JOI sammelt leidenschaftlich gern Bilder und besitzt bereits viele davon. Kürzlich bemerkte er, dass der Speicherplatz seiner Festplatte knapp wird, weil er zu viele Bilder gesammelt hat. Er hat kein Geld für eine neue Festplatte, aber seine Bilder zu löschen wäre für ihn unerträglich. Deshalb beschließt er, die Bilder geschickt zu komprimieren, um Speicherplatz zu sparen.

Ein Bild besteht aus insgesamt $2^N\times2^N$ Pixeln, die quadratisch in $2^N$ Zeilen und $2^N$ Spalten angeordnet sind. Jedes Pixel ist entweder weiß oder schwarz.

JOI möchte solche Bilder mit der folgenden Methode komprimieren.

• Haben alle Pixel des Bildes dieselbe Farbe, wird nur diese Farbe gespeichert. Die Größe der komprimierten Daten beträgt dann $1$.
• Andernfalls wird das Bild in vier kleinere Bilder aufgeteilt. Hat es $2^k$ Zeilen und $2^k$ Spalten, wird es in der Mitte sowohl waagerecht als auch senkrecht geteilt. So entstehen vier Bilder mit jeweils $2^{k-1}$ Zeilen und $2^{k-1}$ Spalten. Diese vier kleineren Bilder werden mit derselben Methode komprimiert. Die Größe der komprimierten Daten ist dann die Summe der komprimierten Datengrößen dieser vier Bilder plus $1$.

JOI ist unsicher, ob diese Methode die Bilder tatsächlich komprimiert. Deshalb möchte er mit verschiedenen Bildern experimentieren. Das Experiment verläuft folgendermaßen.

• Zunächst wird ein Bild vorbereitet, dessen Pixel alle weiß sind.
• Für $i=1,\ldots,Q$ wird folgende Operation ausgeführt: Falls $T_i=0$, werden die Farben aller $2^N$ Pixel in Zeile $X_i$ von oben umgekehrt; falls $T_i=1$, werden die Farben aller $2^N$ Pixel in Spalte $X_i$ von links umgekehrt. Bezeichnen wir die Position in Zeile $a$ von oben und Spalte $b$ von links mit $(a,b)$, so werden bei $T_i=0$ die Pixel $(X_i,b)$ mit $1\le b\le2^N$ und bei $T_i=1$ die Pixel $(a,X_i)$ mit $1\le a\le2^N$ jeweils von weiß nach schwarz beziehungsweise von schwarz nach weiß geändert.
• Für jedes $i$ wird die Datengröße bestimmt, die entsteht, wenn das Bild nach der Operation $i$ mit JOIs Methode komprimiert wird.

Damit im Experiment möglichst viele Operationen durchgeführt werden können, muss die komprimierte Datengröße schnell bestimmt werden.

Aufgabe

Schreibe ein Programm, das die ganze Zahl $N$ zur Beschreibung der Bildgröße, die Anzahl der Operationen $Q$ und die Anweisungen für diese $Q$ Operationen erhält und nach jeder Operation die Datengröße bestimmt, die beim Komprimieren des Bildes mit JOIs Methode entsteht.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen $N,Q$. Das Bild hat $2^N$ Zeilen und $2^N$ Spalten, und es werden $Q$ Operationen durchgeführt.
• Die folgenden $Q$ Zeilen beschreiben die Operationen. Zeile $i$ ($1\le i\le Q$) davon enthält zwei durch Leerzeichen getrennte ganze Zahlen $T_i,X_i$ mit $0\le T_i\le1$ und $1\le X_i\le2^N$. Bei Operation $i$ werden für $T_i=0$ die Farben aller Pixel in Zeile $X_i$ von oben und für $T_i=1$ die Farben aller Pixel in Spalte $X_i$ von links umgekehrt.

Ausgabe

Gib $Q$ Zeilen auf der Standardausgabe aus. Zeile $i$ ($1\le i\le Q$) soll eine ganze Zahl enthalten: die Größe der komprimierten Daten für das Bild nach Operation $i$ bei Verwendung von JOIs Methode.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $1\le N\le20$.
• $1\le Q\le2\,000\,000$.

Teilaufgaben

Teilaufgabe 1 [10 Punkte]

Die folgenden Bedingungen gelten.

• $N\le6$.
• $Q\le128$.

Teilaufgabe 2 [20 Punkte]

Die folgenden Bedingungen gelten.

• $N\le10$.
• $Q\le2\,048$.

Teilaufgabe 3 [70 Punkte]

• Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

2 3
0 1
1 2
0 3

Ausgabe 1

13
17
21

Hinweis

In diesem Beispiel werden die $Q=3$ Operationen wie folgt durchgeführt.

Ausgangszustand