Loid Forger a primit o nouă misiune: să saboteze o mină importantă de lângă Berlint, Ostania. Mina are forma unei coloane verticale împărțită pe n niveluri, numerotate de la 1 (cel mai de sus nivel) la n (cel mai de jos). Fiecare nivel conține aer (care are codul 0), nisip (care are codul 1) sau piatră (care are codul 2).

Misiunea lui Loid constă în a dinamita piatra de pe unele niveluri pentru a provoca surparea minei și curgerea nisipului spre nivelurile inferioare. El are de îndeplinit m sarcini numerotate de la 1 la m. Acestea sunt de două tipuri:

• 1 t p (dinamitare): Loid trebuie ca, la secunda t, să dinamiteze piatra de pe nivelul p al minei. Pentru orice astfel de sarcină, Loid știe că, la secunda t, nivelul p conține piatră, iar aceasta va fi înlocuită de aer la secunda t+1, după dinamitare.
• 2 t p (întrebare): Pentru a i se testa perspicacitatea, Loid este întrebat ce conține nivelul p al minei la secunda t: aer, nisip sau piatră?

În general, conținutul unui nivel la secunda t va fi același și la secunda t+1, cu două excepții:

• Curgerea nisipului: dacă, la secunda t, nivelul p conține nisip și nivelul p+1 conține aer, nisipul va curge și, la secunda t+1, nivelul p conține aer și nivelul p+1 conține nisip.
• Dinamitarea de către Loid: un nivel care conține piatră și este dinamitat la secunda t va conține aer la secunda t+1.

Dacă la secunda t fiecare nivel i de la 1 la n al minei are același conținut ca la secunda t-1, spunem că mina este stabilă la secunda t.

Cerința

Dându-se n, conținuturile tuturor nivelurilor minei la secunda 0, m și sarcinile care trebuie îndeplinite, să se determine răspunsurile la sarcinile de tip întrebare.

Date de intrare

Fișierul de intrare nisip.in conține pe prima linie două numere naturale n și m separate printr-un spațiu, reprezentând numărul de niveluri ale minei, respectiv numărul de sarcini. Pe următoarea linie se vor afla n numere naturale separate prin câte un spațiu, al i-ulea dintre acestea reprezentând codul conținutul nivelului i al minei (0 pentru aer, 1 pentru nisip, 2 pentru piatră). Următoarele m linii conțin descrierile sarcinilor din cadrul misiunii lui Loid. A i-a dintre acestea va conține trei numere naturale ci, ti și pi separate printr-un spațiu, reprezentând, în ordine cronologică, sarcinile date lui Loid: ci reprezintă tipul sarcinii i (1 pentru dinamitare, 2 pentru întrebare), ti reprezintă secunda și pi reprezintă nivelul minei.

Date de ieșire

Fișierul de ieșire nisip.out va conține codurile corespunzătoare răspunsurilor la sarcinile de tip întrebare (0 pentru aer, 1 pentru nisip, 2 pentru piatră), în ordinea din fișierul de intrare, câte unul pe fiecare linie.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• 1 ≤ m ≤ 1.000.000
• 1 ≤ ti ≤ 1.000.000.000 și 1 ≤ pi ≤ n pentru orice i, 1 ≤ i ≤ m.
• ti < ti+1, pentru orice i, 1 ≤ i < m.
• Nivelul n conține întotdeauna piatră și Loid nu va avea niciodată sarcina de a dinamita piatra de pe nivelul n.
• Mina este stabilă la secunda 1.
• Pentru fiecare sarcină i pentru care ci = 1, mina este stabilă la secunda ti.

Exemplu:

nisip.in

6 4
0 1 1 2 0 2
1 1 4
2 2 3
2 4 2
2 5 4

nisip.out

1
0
1

Explicație

Conținuturile nivelurilor minei sunt:

• 0 1 1 2 0 2 la secunda 1,
• 0 1 1 0 0 2 la secunda 2,
• 0 1 0 1 0 2 la secunda 3,
• 0 0 1 0 1 2 la secunda 4,
• 0 0 0 1 1 2 la secunda 5,
• 0 0 0 1 1 2 la secunda 6, etc.