== include(page="template/taskheader" task_id="undo2") ==
XORin este nemulţumit de problemele primite în prima zi de concurs de la Olimpiada Naţională de Informatică şi decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din şiruri de numere. Din când în când el trebuie să adauge sau să şteargă elemente din şir. Câteodată el decide să readauge dintre elemente şterse anterior. Fie şirul de numere a=(a 1 , a 2 , ... ,a N ) şi N numărul de elemente din şir după fiecare operaţie.
$XORin$ este nemulţumit de problemele primite în prima zi de concurs de la $Olimpiada Naţională de Informatică$ şi decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din şiruri de numere. Din când în când el trebuie să adauge sau să şteargă elemente din şir. Câteodată el decide să readauge dintre elemente şterse anterior. Fie şirul de numere $a$ = (a ~1~ , a ~2~ , ... ,a ~N~ ) şi $N$ numărul de elemente din şir după fiecare operaţie.
Astfel el are de realizat următoarele operaţii pornind de la un şir vid:
* Inserează la sfârşitul şirului o valoare x;
* Şterge ultimele x elemente din şir;
* Readaugă la sfârşitul şirului primele x elemente şterse. Dacă, de exemplu, în operaţia anterioară de ştergere a unui număr y de elemente, am şters elementele a N-y+1 , a N-y+2 ,..., a N , iar acum urmează o operaţie de readăugare a x elemente, vor fi adăugate în ordine elementele a N-y+1 , a N-y+2 ,..., a N-y+x la sfârşitul şirului.
* Inserează la sfârşitul şirului o valoare $x$;
* Şterge ultimele $x$ elemente din şir;
* Readaugă la sfârşitul şirului primele $x$ elemente şterse. Dacă, de exemplu, în operaţia anterioară de ştergere a unui număr $y$ de elemente, am şters elementele a ~N-y+1~ , a ~N-y+2~ ,..., a ~N~ , iar acum urmează o operaţie de readăugare a $x$ elemente, vor fi adăugate în ordine elementele a ~N-y+1~ , a ~N-y+2~ ,..., a ~N-y+x~ la sfârşitul şirului.
Din când în când XORin îşi pune următoarea întrebare: de câte ori există valoarea x în şir?
Din când în când $XORin$ îşi pune următoarea întrebare: de câte ori există valoarea $x$ în şir?
h2. Date de intrare
Pe prima linie a fişierului undo.in se va afla M ce reprezintă numărul de operaţii.
Pe următoarele M linii se vor afla operaţiile codificate astfel:
1 x - se inserează elementul x la sfârşitul şirului
2 y - se şterg ultimele y elemente adăugate în şir
3 z - se adaugă înapoi la sfârşitul şirului primele z elemente şterse
4 t - se afişează numărul de elemente cu valoarea t din şir
Pe prima linie a fişierului $undo2.in$ se va afla $M$ ce reprezintă numărul de operaţii.
Pe următoarele $M$ linii se vor afla operaţiile codificate astfel:
$1 x$ - se inserează elementul $x$ la sfârşitul şirului
$2 y$ - se şterg ultimele $y$ elemente adăugate în şir
$3 z$ - se adaugă înapoi la sfârşitul şirului primele $z$ elemente şterse
$4 t$ - se afişează numărul de elemente cu valoarea $t$ din şir
h2. Date de ieşire
Pe fiecare linie a fişierului undo.out se scriu răspunsurile la întrebările lui XORin, fiecare răspuns pe câte o linie.
Pe fiecare linie a fişierului $undo2.out$ se scriu răspunsurile la întrebările lui $XORin$, fiecare răspuns pe câte o linie.
h2. Restricţii
* Toate numerele din fişierul de intrare sunt cuprinse între 1 şi 200 000;
* Pentru 20% din teste se garantează M ≤ 1 000, pentru alte 40% din teste, se garantează că numerele inserate vor fi distincte;
* Între o operaţie de ştergere şi una de readăugare sau între două de readăugare nu se vor afla alte operaţii de inserare
* Toate numerele din fişierul de intrare sunt cuprinse între $1$ şi $200 000$;
* Pentru $20%$ din teste se garantează $M ≤ 1 000$, pentru alte $40%$ din teste, se garantează că numerele inserate vor fi distincte;
* Între o operaţie de readăugare si operatia anterioară de stergere nu vor exista operatii de inserare.
* Numărul de elemente readăugate nu va fi mai mare decât numărul de elemente şterse la ultima operaţie.
* Între două operaţii de readăugare va exista cel puţin o operaţie de ştergere.
