JOI ama collezionare immagini e ne possiede molte. Di recente, JOI si è reso conto che il suo disco rigido sta esaurendo lo spazio perché ha collezionato troppe immagini. Non può permettersi di comprare un nuovo disco rigido, e cancellare anche una sola delle sue immagini è estremamente doloroso per lui, quindi ha deciso di comprimere le sue immagini per risparmiare spazio.

Un'immagine è rappresentata da un totale di $2^N \times 2^N$ pixel disposti in una griglia quadrata di $2^N$ righe e $2^N$ colonne. Ogni pixel è bianco oppure nero.

JOI ha deciso di comprimere tale immagine usando il seguente metodo:

• Se tutti i pixel nell'immagine sono dello stesso colore, registra solo quel colore. In questo caso, la dimensione dei dati compressi è $1$.
• Altrimenti, dividi l'immagine in quattro immagini più piccole. Se l'immagine ha $2^k$ righe e $2^k$ colonne, dividi l'immagine al centro sia verticalmente che orizzontalmente per ottenere quattro immagini di $2^{k-1}$ righe e $2^{k-1}$ colonne. Comprimi queste quattro immagini più piccole usando lo stesso metodo. In questo caso, la dimensione dei dati compressi è la somma delle dimensioni dei dati compressi delle quattro immagini più piccole, più $1$.

JOI è diventato ansioso riguardo al fatto che questo metodo possa davvero comprimere le immagini, quindi ha deciso di fare degli esperimenti con varie immagini. Il metodo sperimentale è il seguente:

• Per prima cosa, prepara un'immagine in cui tutti i pixel sono bianchi.
• Per $i = 1, \dots, Q$, esegui la seguente operazione: "Se $T_i = 0$, inverti i colori (da bianco a nero, da nero a bianco) di tutti i $2^N$ pixel nella $X_i$-esima riga dall'alto. Se $T_i = 1$, inverti i colori di tutti i $2^N$ pixel nella $X_i$-esima colonna da sinistra." Cioè, se indichiamo il pixel alla $a$-esima riga dall'alto e $b$-esima colonna da sinistra con $(a, b)$, per ogni $i$, se $T_i = 0$, esegui l'operazione sui pixel $(X_i, b)$ per tutti gli $1 \le b \le 2^N$, e se $T_i = 1$, esegui l'operazione sui pixel $(a, X_i)$ per tutti gli $1 \le a \le 2^N$.
• Per ogni $i$, determina la dimensione dei dati compressi quando l'immagine dopo la $i$-esima operazione viene compressa usando il metodo di JOI.

Per eseguire il maggior numero possibile di operazioni nell'esperimento, è necessario determinare la dimensione dei dati compressi ad alta velocità.

Compito

Dato un intero $N$ che rappresenta la dimensione dell'immagine, il numero di operazioni $Q$ e le istruzioni per le $Q$ operazioni, scrivi un programma che calcoli la dimensione dei dati compressi dopo ogni operazione usando il metodo di JOI.

Input

Leggi quanto segue dallo standard input:

• La prima riga contiene due interi $N$ e $Q$, separati da uno spazio, che indicano che l'immagine ha dimensione $2^N \times 2^N$ e che ci sono $Q$ operazioni.
• Le successive $Q$ righe contengono le istruzioni per le operazioni. La $i$-esima riga ($1 \le i \le Q$) contiene due interi $T_i$ e $X_i$ ($0 \le T_i \le 1$ e $1 \le X_i \le 2^N$), separati da uno spazio, che indicano che la $i$-esima operazione inverte i colori di tutti i pixel nella $X_i$-esima riga dall'alto se $T_i = 0$, oppure nella $X_i$-esima colonna da sinistra se $T_i = 1$.

Output

Stampa $Q$ righe sullo standard output. La $i$-esima riga ($1 \le i \le Q$) deve contenere un singolo intero che rappresenta la dimensione dei dati compressi dopo la $i$-esima operazione.

Limiti

Tutti i dati di input soddisfano le seguenti condizioni:

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

Sottoproblemi

Sottoproblema 1 [10 punti]

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

Sottoproblema 2 [20 punti]

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

Sottoproblema 3 [70 punti]

• Nessuna limitazione aggiuntiva.

Esempi

Input 1

2 3
0 1
1 2
0 3

Output 1

13
17
21

Note

In questo esempio, le $Q = 3$ operazioni vengono eseguite come segue:

Stato iniziale: □□□□ □□□□ □□□□ □□□□ ↓ ■■■■ □□□□ □□□□ □□□□ ↓ ■□■■ □■□□ □■□□ □■□□ ↓ ■□■■ □■□□ ■□■■ □■□□