ostasi

Pe data de 15 iulie 1475, în pragul unei mari bătălii, Ștefan cel Mare – marele strateg al Moldovei – își pregătește armata. Ostaşii sunt organizați în $n$ trupe, numerotate de la $1$ la $n$. Inițial toţi ostaşii din fiecare trupă au nivelul de experiență $0$.

Puterea unei trupe $i$ ($1 \le i \le n$), notată cu $P_i$, este egală cu cel mai mic nivel de experienţă care lipseşte din trupa respectivă. Iniţial, puterea fiecărei trupe este prin urmare $1$.

Pentru a obține un avantaj tactic decisiv, domnitorul emite o listă cu două tipuri de comenzi către hatmanul său de încredere, Jean Carapace:

Cerință

Scrieţi un program care execută comenzile din lista primită de hatmanul Jean Carapace.

Date de intrare

Fişierul de intrare ostasi.in conţine pe prima linie numerele naturale $n$ și $q$, separate printr-un spaţiu, unde $n$ reprezintă numărul de trupe, iar $q$ reprezintă numărul de comenzi din listă. Pe următoarele $q$ linii sunt scrise cele $q$ comenzi, câte o comandă pe o linie, în ordinea în care trebuie să fie executate, în formatul descris în enunţ.

Date de ieșire

Fişierul de ieşire ostasi.out va conţine numerele naturale afişate după executarea în ordine a comenzilor din listă, câte un număr pe o linie.

Restricții și precizări

• $1 \le n, q, val \le 200\ 000$

Exemplu

ostasi.in

6 10
2 1 4 1
1 1
2 3 6 1
1 2
2 2 4 1
1 2
2 4 5 1
2 3 6 4
1 3
1 4

ostasi.out

2
1
3
5
6

Explicație

Iniţial cele $6$ trupe au mulţimea nivelurilor de experienţă $0$.

Lista conţine $10$ comenzi. După executarea primei comenzi, trupele $i$ ($1 \le i \le 4$) primesc câte un ostaş cu nivelul de experienţă $1+(i-1)$.

Cel mai mic nivel de experienţă care lipseşte acum din trupa $1$ este $2$, deci după executarea celei de a doua comenzi se va afişa $2$.

După executarea celei de a treia comenzi, trupele $i$ ($3 \le i \le 6$) primesc câte un ostaş cu nivelul de experienţă $1+(i-3)$.

După executarea celei de a patra comenzi, se va afişa cel mai mic nivel de experienţă care lipseşte din trupa $2$ (adică $1$).

După executarea celei de a cincea comenzi, trupele $i$ ($2 \le i \le 4$) primesc câte un ostaş cu nivelul de experienţă $1+(i-2)$.

După executarea celei de a şasea comenzi, se va afişa cel mai mic nivel de experienţă care lipseşte din trupa $2$ (adică $3$).

După executarea celei de a şaptea comenzi, trupele $i$ ($4 \le i \le 5$) primesc câte un ostaş cu nivelul de experienţă $1+(i-4)$, iar după executarea celei de a opta comenzi trupele $i$ ($3 \le i \le 6$) primesc câte un ostaş cu nivelul de experienţă $4+(i-3)$.

După executarea celei de a noua comenzi se va afişa cel mai mic nivel de experienţă care lipseşte din trupa $3$ (adică $5$).

După executarea celei de a zecea comenzi se va afişa cel mai mic nivel de experienţă care lipseşte din trupa $4$ (adică $6$).