JOI elskar að safna myndum og á mikið af þeim. Nýlega áttaði JOI sig á því að harði diskurinn hans er að verða uppiskroppa með pláss vegna þess að hann hefur safnað of mörgum myndum. Hann hefur ekki efni á að kaupa nýjan harðan disk, og að eyða einhverri af myndunum sínum er afar sársaukafullt fyrir hann, svo hann ákvað að þjappa myndunum sínum til að spara pláss.

Mynd er táknuð með alls $2^N \times 2^N$ dílum (pixlum) sem raðað er í ferhyrnt net með $2^N$ röðum og $2^N$ dálkum. Hver díll er annaðhvort hvítur eða svartur.

JOI ákvað að þjappa slíkri mynd með eftirfarandi aðferð:

• Ef allir dílar í myndinni eru í sama lit, skráðu þá aðeins þann lit. Í þessu tilviki er stærð þjöppuðu gagnanna $1$.
• Annars skaltu skipta myndinni í fjórar minni myndir. Ef myndin hefur $2^k$ raðir og $2^k$ dálka, skiptu þá myndinni í miðjunni bæði lóðrétt og lárétt til að fá fjórar myndir með $2^{k-1}$ röðum og $2^{k-1}$ dálkum. Þjappaðu þessum fjórum minni myndum með sömu aðferð. Í þessu tilviki er stærð þjöppuðu gagnanna summa stærða þjöppuðu gagnanna fyrir minni myndirnar fjórar, plús $1$.

JOI varð áhyggjufullur um hvort þessi aðferð gæti í raun þjappað myndum, svo hann ákvað að gera tilraunir með ýmsar myndir. Tilraunaaðferðin er sem hér segir:

• Undirbúðu fyrst mynd þar sem allir dílar eru hvítir.
• Fyrir $i = 1, \dots, Q$, framkvæmdu eftirfarandi aðgerð: "Ef $T_i = 0$, snúðu við litunum (hvítum í svartan, svörtum í hvítan) á öllum $2^N$ dílunum í $X_i$-tu röðinni að ofan. Ef $T_i = 1$, snúðu við litunum á öllum $2^N$ dílunum í $X_i$-ta dálkinum frá vinstri." Það er, ef við táknum dílinn í $a$-tu röð að ofan og $b$-ta dálki frá vinstri sem $(a, b)$, þá skal fyrir hvert $i$, ef $T_i = 0$, framkvæma aðgerðina á díla $(X_i, b)$ fyrir öll $1 \le b \le 2^N$, og ef $T_i = 1$, framkvæma aðgerðina á díla $(a, X_i)$ fyrir öll $1 \le a \le 2^N$.
• Fyrir hvert $i$, ákvarðaðu stærð þjöppuðu gagnanna þegar myndin eftir $i$-tu aðgerðina er þjöppuð með aðferð JOI.

Til að framkvæma sem flestar aðgerðir í tilrauninni er nauðsynlegt að ákvarða stærð þjöppuðu gagnanna á miklum hraða.

Verkefni

Gefin er heiltala $N$ sem táknar stærð myndarinnar, fjöldi aðgerða $Q$ og fyrirmæli fyrir $Q$ aðgerðir. Skrifið forrit sem reiknar út stærð þjöppuðu gagnanna eftir hverja aðgerð með aðferð JOI.

Inntak

Lesið eftirfarandi úr staðalinntaki:

• Fyrsta línan inniheldur tvær heiltölur $N$ og $Q$, aðskildar með bili, sem tákna að myndin sé af stærð $2^N \times 2^N$ og að það séu $Q$ aðgerðir.
• Næstu $Q$ línur innihalda fyrirmælin fyrir aðgerðirnar. $i$-ta línan ($1 \le i \le Q$) inniheldur tvær heiltölur $T_i$ og $X_i$ ($0 \le T_i \le 1$ og $1 \le X_i \le 2^N$), aðskildar með bili, sem tákna að $i$-ta aðgerðin snúi við litum allra díla í $X_i$-tu röðinni að ofan ef $T_i = 0$, eða í $X_i$-ta dálkinum frá vinstri ef $T_i = 1$.

Úttak

Skrifið $Q$ línur í staðalúttak. $i$-ta línan ($1 \le i \le Q$) á að innihalda eina heiltölu sem táknar stærð þjöppuðu gagnanna eftir $i$-tu aðgerðina.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

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

Undirverkefni

Undirverkefni 1 [10 stig]

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

Undirverkefni 2 [20 stig]

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

Undirverkefni 3 [70 stig]

• Engar viðbótarskorður.

Dæmi

Inntak 1

2 3
0 1
1 2
0 3

Úttak 1

13
17
21

Athugasemd

Í þessu dæmi eru $Q = 3$ aðgerðirnar framkvæmdar sem hér segir:

Upphafsstaða: □□□□ □□□□ □□□□ □□□□ ↓ ■■■■ □□□□ □□□□ □□□□ ↓ ■□■■ □■□□ □■□□ □■□□ ↓ ■□■■ □■□□ ■□■■ □■□□