Cerința

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.

Din când în când XORin își pune următoarea întrebare: de câte ori există valoarea x în șir?

Date de intrare

Fișierul de intrare undo.in conține pe prima linie numărul 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

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.

Restricții și precizări

• Toate numerele din fișierul de intrare sunt cuprinse între 1 și 200000;
• Pentru 20% din teste se garantează M ≤ 1000, 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
• 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.

Exemplu:

undo.in

16
1 1
1 2
1 3
1 4
4 4
2 2
4 3
3 1
4 4
4 3
1 7
1 7
1 7
4 7
2 2
4 7

undo.out

1
0
0
1
3
1

Explicație

Inițial șirul este vid.
După primele 4 operații de inserare șirul este 1, 2, 3, 4.
Operația 4 4 va afișa 1.
Operația 2 2 va șterge ultimele două elemente șirul devenind 1, 2.
Din cauză că elementul 3 a fost șters, a șaptea operație va afișa 0.
Operația 3 1 va readăuga la sfârșitul șirului elementul 3.
În urma acestei operații șirul devine 1, 2, 3.
Operația 4 4 va afișa 0, iar operația 4 3 va afișa 1.
ș.a.m.d.