Collecting Images is Fun

JOI loves collecting images and has a lot of them. Recently he noticed that he has collected too many images and his hard disk is running low on space. He does not have the money to buy a new hard disk, and deleting the images he owns would pain him more than anything, so he decided to compress the images well and reduce the space they take.

An image is represented by $2^N \times 2^N$ pixels arranged in a square with $2^N$ rows and $2^N$ columns. Each pixel is either white or black.

JOI decided to compress such an image in the following way.

• If all pixels in the image have the same color, record only that color. The size of the compressed data is then 1.
• Otherwise, split the image into 4 smaller images. If the image has $2^k$ rows and $2^k$ columns, split it at the center both vertically and horizontally to obtain 4 images with $2^{k-1}$ rows and $2^{k-1}$ columns. Compress these 4 smaller images in the same way. The size of the compressed data is then the sum of the sizes of the compressed data of the 4 smaller images, plus 1.

JOI became worried about whether this method really compresses images, so he decided to experiment with various images. The experiment works as follows.

• First, prepare an image in which every pixel is white.
• For $i = 1, \dots, Q$, perform the operation: "if $T_i = 0$, invert the colors of the $2^N$ pixels in the $X_i$-th row counted from the top; if $T_i = 1$, invert the colors of the $2^N$ pixels in the $X_i$-th column counted from the left." That is, writing the pixel in row $a$ from the top and column $b$ from the left as $(a, b)$, for each $i$: if $T_i = 0$, then for every pixel $(X_i, b)$ with $1 \le b \le 2^N$, and if $T_i = 1$, then for every pixel $(a, X_i)$ with $1 \le a \le 2^N$, change white pixels to black and black pixels to white.
• For each $i$, find the size of the compressed data when the image after the $i$-th operation is compressed by JOI's method.

To perform as many operations as possible in the experiment, the size of the compressed data must be found quickly.

Given the integer $N$ representing the image size, the number of operations $Q$, and the instructions for the $Q$ operations, write a program that finds the size of the compressed data when the image after each operation is compressed by JOI's method.

Read the following input from standard input.

• The first line contains two integers $N, Q$ separated by a space, representing that the image has $2^N$ rows and $2^N$ columns and that $Q$ operations are performed.
• The following $Q$ lines contain the operation instructions. The $i$-th of these $Q$ lines ($1 \le i \le Q$) contains two integers $T_i, X_i$ ($0 \le T_i \le 1$ and $1 \le X_i \le 2^N$) separated by a space, representing that the $i$-th operation inverts the colors of all pixels in the $X_i$-th row from the top if $T_i = 0$, or in the $X_i$-th column from the left if $T_i = 1$.

Output $Q$ lines to standard output. The $i$-th line ($1 \le i \le Q$) contains a single integer: the size of the compressed data when the image after the $i$-th operation is compressed by JOI's method.

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