JOI älskar att samla på bilder och äger många sådana. Nyligen insåg JOI att hans hårddisk håller på att få slut på utrymme eftersom han har samlat på sig för många bilder. Han har inte råd att köpa en ny hårddisk, och att radera någon av sina bilder är extremt smärtsamt för honom, så han bestämde sig för att komprimera sina bilder för att spara utrymme.

En bild representeras av totalt $2^N \times 2^N$ pixlar arrangerade i ett kvadratiskt rutnät med $2^N$ rader och $2^N$ kolumner. Varje pixel är antingen vit eller svart.

JOI bestämde sig för att komprimera en sådan bild med följande metod:

• Om alla pixlar i bilden har samma färg, spara bara den färgen. I detta fall är storleken på den komprimerade datan $1$.
• Annars, dela upp bilden i fyra mindre bilder. Om bilden har $2^k$ rader och $2^k$ kolumner, dela bilden i mitten både vertikalt och horisontellt för att få fyra bilder med $2^{k-1}$ rader och $2^{k-1}$ kolumner. Komprimera dessa fyra mindre bilder med samma metod. I detta fall är storleken på den komprimerade datan summan av storlekarna på den komprimerade datan för de fyra mindre bilderna, plus $1$.

JOI blev orolig över huruvida denna metod verkligen kunde komprimera bilder, så han bestämde sig för att experimentera med olika bilder. Experimentmetoden är som följer:

• Förbered först en bild där alla pixlar är vita.
• För $i = 1, \dots, Q$, utför följande operation: "Om $T_i = 0$, invertera färgerna (vitt till svart, svart till vitt) på alla $2^N$ pixlar på den $X_i$-te raden uppifrån. Om $T_i = 1$, invertera färgerna på alla $2^N$ pixlar i den $X_i$-te kolumnen från vänster." Det vill säga, om vi betecknar pixeln på den $a$-te raden uppifrån och $b$-te kolumnen från vänster som $(a, b)$, utför för varje $i$, om $T_i = 0$, operationen på pixlarna $(X_i, b)$ för alla $1 \le b \le 2^N$, och om $T_i = 1$, utför operationen på pixlarna $(a, X_i)$ för alla $1 \le a \le 2^N$.
• För varje $i$, bestäm storleken på den komprimerade datan när bilden efter den $i$-te operationen komprimeras med JOI:s metod.

För att kunna utföra så många operationer som möjligt i experimentet är det nödvändigt att bestämma storleken på den komprimerade datan med hög hastighet.

Uppgift

Givet ett heltal $N$ som representerar bildens storlek, antalet operationer $Q$ samt instruktionerna för $Q$ operationer, skriv ett program som beräknar storleken på den komprimerade datan efter varje operation med JOI:s metod.

Indata

Läs följande från standard inmatning:

• Den första raden innehåller två heltal $N$ och $Q$, separerade med ett blanksteg, vilket representerar att bilden har storleken $2^N \times 2^N$ och att det finns $Q$ operationer.
• De följande $Q$ raderna innehåller instruktionerna för operationerna. Den $i$-te raden ($1 \le i \le Q$) innehåller två heltal $T_i$ och $X_i$ ($0 \le T_i \le 1$ och $1 \le X_i \le 2^N$), separerade med ett blanksteg, vilket representerar att den $i$-te operationen inverterar färgerna på alla pixlar på den $X_i$-te raden uppifrån om $T_i = 0$, eller i den $X_i$-te kolumnen från vänster om $T_i = 1$.

Utdata

Skriv ut $Q$ rader till standard utmatning. Den $i$-te raden ($1 \le i \le Q$) ska innehålla ett enda heltal som representerar storleken på den komprimerade datan efter den $i$-te operationen.

Begränsningar

Alla indata uppfyller följande villkor:

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

Deluppgifter

Deluppgift 1 [10 poäng]

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

Deluppgift 2 [20 poäng]

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

Deluppgift 3 [70 poäng]

• Inga ytterligare begränsningar.

Exempel

Indata 1

2 3
0 1
1 2
0 3

Utdata 1

13
17
21

Anmärkning

I detta exempel utförs de $Q = 3$ operationerna enligt följande:

Starttillstånd: □□□□ □□□□ □□□□ □□□□ ↓ ■■■■ □□□□ □□□□ □□□□ ↓ ■□■■ □■□□ □■□□ □■□□ ↓ ■□■■ □■□□ ■□■■ □■□□