JOI elsker å samle på bilder og eier mange av dem. Nylig innså JOI at harddisken hans begynner å gå tom for plass fordi han har samlet for mange bilder. Han har ikke råd til å kjøpe en ny harddisk, og å slette noen av bildene sine er ekstremt smertefullt for ham, så han bestemte seg for å komprimere bildene sine for å spare plass.

Et bilde representeres av totalt $2^N \times 2^N$ piksler arrangert i et kvadratisk rutenett med $2^N$ rader og $2^N$ kolonner. Hver piksel er enten hvit eller svart.

JOI bestemte seg for å komprimere et slikt bilde ved hjelp av følgende metode:

• Hvis alle pikslene i bildet har samme farge, registrer bare den fargen. I dette tilfellet er størrelsen på de komprimerte dataene $1$.
• Ellers, del bildet inn i fire mindre bilder. Hvis bildet har $2^k$ rader og $2^k$ kolonner, del bildet på midten både vertikalt og horisontalt for å få fire bilder med $2^{k-1}$ rader og $2^{k-1}$ kolonner. Komprimer disse fire mindre bildene ved hjelp av samme metode. I dette tilfellet er størrelsen på de komprimerte dataene summen av størrelsene på de komprimerte dataene for de fire mindre bildene, pluss $1$.

JOI ble bekymret for om denne metoden virkelig kunne komprimere bilder, så han bestemte seg for å eksperimentere med ulike bilder. Eksperimentmetoden er som følger:

• Forbered først et bilde der alle pikslene er hvite.
• For $i = 1, \dots, Q$, utfør følgende operasjon: "Hvis $T_i = 0$, inverter fargene (hvitt til svart, svart til hvitt) på alle de $2^N$ pikslene i den $X_i$-te raden ovenfra. Hvis $T_i = 1$, inverter fargene på alle de $2^N$ pikslene i den $X_i$-te kolonnen fra venstre." Det vil si, hvis vi betegner pikselen på den $a$-te raden ovenfra og den $b$-te kolonnen fra venstre som $(a, b)$, utfør for hver $i$, hvis $T_i = 0$, operasjonen på pikslene $(X_i, b)$ for alle $1 \le b \le 2^N$, og hvis $T_i = 1$, utfør operasjonen på pikslene $(a, X_i)$ for alle $1 \le a \le 2^N$.
• For hver $i$, bestem størrelsen på de komprimerte dataene når bildet etter den $i$-te operasjonen komprimeres med JOIs metode.

For å utføre så mange operasjoner som mulig i eksperimentet, er det nødvendig å bestemme størrelsen på de komprimerte dataene med høy hastighet.

Oppgave

Gitt et heltall $N$ som representerer størrelsen på bildet, antall operasjoner $Q$, og instruksjonene for $Q$ operasjoner, skriv et program som beregner størrelsen på de komprimerte dataene etter hver operasjon ved hjelp av JOIs metode.

Inndata

Les følgende fra standard inndata:

• Den første linjen inneholder to heltall $N$ og $Q$, adskilt med et mellomrom, som representerer at bildet har størrelse $2^N \times 2^N$ og at det er $Q$ operasjoner.
• De påfølgende $Q$ linjene inneholder instruksjonene for operasjonene. Den $i$-te linjen ($1 \le i \le Q$) inneholder to heltall $T_i$ og $X_i$ ($0 \le T_i \le 1$ og $1 \le X_i \le 2^N$), adskilt med et mellomrom, som representerer at den $i$-te operasjonen inverterer fargene på alle pikslene i den $X_i$-te raden ovenfra hvis $T_i = 0$, eller i den $X_i$-te kolonnen fra venstre hvis $T_i = 1$.

Utdata

Skriv ut $Q$ linjer til standard utdata. Den $i$-te linjen ($1 \le i \le Q$) skal inneholde et enkelt heltall som representerer størrelsen på de komprimerte dataene etter den $i$-te operasjonen.

Begrensninger

Alle inndata oppfyller følgende betingelser:

• $1 \le N \le 20$.
• $1 \le Q \le 2\,000\,000$.

Deloppgaver

Deloppgave 1 [10 poeng]

• $N \le 6$.
• $Q \le 128$.

Deloppgave 2 [20 poeng]

• $N \le 10$.
• $Q \le 2048$.

Deloppgave 3 [70 poeng]

• Ingen ytterligere begrensninger.

Eksempler

Inndata 1

2 3
0 1
1 2
0 3

Utdata 1

13
17
21

Merk

I dette eksempelet utføres de $Q = 3$ operasjonene som følger:

Starttilstand: □□□□ □□□□ □□□□ □□□□ ↓ ■■■■ □□□□ □□□□ □□□□ ↓ ■□■■ □■□□ □■□□ □■□□ ↓ ■□■■ □■□□ ■□■■ □■□□