nisip

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$.

Cerintă

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 va 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 $c_i$, $t_i$ și $p_i$ separate printr-un spațiu, reprezentând, în ordine cronologică, sarcinile date lui Loid: $c_i$ reprezintă tipul sarcinii $i$ ($1$ pentru dinamitare, $2$ pentru întrebare), $t_i$ reprezintă secunda și $p_i$ reprezintă nivelul minei.

Date de ieșire

Fișierul de ieșire nisip.out 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

• $1 \leq n \leq 1\ 000\ 000$
• $1 \leq m \leq 1\ 000\ 000$
• $1 \leq t_i \leq 1\ 000\ 000\ 000$ și $1 \leq p_i \leq n$ pentru orice $i$, $1 \leq i \leq m$.
• $t_i < t_{i+1}$, pentru orice $i$, $1 \leq i \leq 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 $c_i = 1$, mina este stabilă la secunda $t_i$.

Exemple

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ții

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.