JOI 君 adore collectionner beaucoup d'images et en possède déjà un grand nombre. Récemment, JOI 君 a remarqué qu'à force d'en accumuler, son disque dur commençait à manquer d'espace. Il n'a pas l'argent nécessaire pour acheter un nouveau disque dur, mais supprimer les images qu'il possède serait pour lui une souffrance insupportable. Il a donc décidé de réduire l'espace occupé en compressant efficacement ses images.

Une image est constituée de $2^N$ lignes et de $2^N$ colonnes de pixels disposés en carré, soit un total de $2^N\times 2^N$ pixels. Chaque pixel est blanc ou noir.

JOI 君 a décidé de compresser ces images de la manière suivante.

• Si tous les pixels de l'image ont la même couleur, seule cette couleur est enregistrée. Dans ce cas, la taille des données compressées est $1$.
• Sinon, l'image est divisée en 4 images plus petites. Si elle comporte $2^k$ lignes et $2^k$ colonnes, on la coupe en son milieu verticalement et horizontalement pour obtenir 4 images comportant chacune $2^{k-1}$ lignes et $2^{k-1}$ colonnes. Ces quatre petites images sont compressées selon la même méthode. Dans ce cas, la taille des données compressées est définie comme la somme des tailles des données compressées des quatre petites images, augmentée de $1$.

JOI 君 s'est demandé si cette méthode permettait réellement de compresser les images et a décidé de réaliser des expériences sur différentes images. La procédure expérimentale est la suivante.

• On prépare d'abord une image dont tous les pixels sont blancs.
• Pour $i=1,\ldots,Q$, on effectue l'opération suivante : si $T_i=0$, on inverse le noir et le blanc des $2^N$ pixels de la ligne $X_i$ en comptant depuis le haut ; si $T_i=1$, on inverse le noir et le blanc des $2^N$ pixels de la colonne $X_i$ en comptant depuis la gauche. Autrement dit, notons $(a,b)$ le pixel situé à la ligne $a$ depuis le haut et à la colonne $b$ depuis la gauche. Pour chaque $i$, si $T_i=0$, on modifie les pixels $(X_i,b)$ tels que $1\le b\le 2^N$ ; si $T_i=1$, on modifie les pixels $(a,X_i)$ tels que $1\le a\le 2^N$. Les pixels blancs deviennent noirs et les pixels noirs deviennent blancs.
• Pour chaque $i$, on détermine la taille des données obtenues en compressant par la méthode de JOI 君 l'image après la $i$-ième opération.

Afin d'effectuer autant d'opérations que possible au cours de l'expérience, il faut déterminer rapidement la taille des données compressées.

Tâche

Étant donnés l'entier $N$ représentant la taille de l'image, le nombre d'opérations $Q$ et les instructions des $Q$ opérations, écrivez un programme qui détermine, après chaque opération, la taille des données obtenues en compressant l'image par la méthode de JOI 君.

Entrée

Lisez les données suivantes depuis l'entrée standard.

• La première ligne contient deux entiers $N,Q$ séparés par un espace. Ils indiquent que l'image comporte $2^N$ lignes et $2^N$ colonnes et que l'on effectue $Q$ opérations.
• Les $Q$ lignes suivantes contiennent les instructions des opérations. La $i$-ième de ces lignes ($1\le i\le Q$) contient deux entiers $T_i,X_i$ séparés par un espace, avec $0\le T_i\le 1$ et $1\le X_i\le 2^N$. Cela signifie que la $i$-ième opération inverse le noir et le blanc de tous les pixels de la ligne $X_i$ depuis le haut si $T_i=0$, ou de la colonne $X_i$ depuis la gauche si $T_i=1$.

Sortie

Écrivez $Q$ lignes sur la sortie standard. Sur la $i$-ième ligne ($1\le i\le Q$), écrivez un entier représentant la taille des données obtenues en compressant, par la méthode de JOI 君, l'image après la $i$-ième opération.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Sous-tâche 1 [10 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 2 [20 points]

Les conditions suivantes sont satisfaites.

• $N\le 10$.
• $Q\le 2\,048$.

Sous-tâche 3 [70 points]

• Aucune contrainte supplémentaire.

Exemples

Entrée 1

2 3
0 1
1 2
0 3

Sortie 1

13
17
21

Remarque

Dans cet exemple, les $Q=3$ opérations sont effectuées de la manière suivante.

L'état initial est représenté tout en haut