JOI loves collecting images and owns many of them. Recently, JOI realized that his hard disk is running out of space because he has collected too many images. He cannot afford to buy a new hard disk, and deleting any of his images is extremely painful for him, so he decided to compress his images to save space.

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

JOI decided to compress such an image using the following method:

• If all pixels in the image are the same color, record only that color. In this case, the size of the compressed data is $1$.
• Otherwise, divide the image into four smaller images. If the image has $2^k$ rows and $2^k$ columns, divide the image at the center both vertically and horizontally to obtain four images of $2^{k-1}$ rows and $2^{k-1}$ columns. Compress these four smaller images using the same method. In this case, the size of the compressed data is the sum of the sizes of the compressed data of the four smaller images, plus $1$.

JOI became anxious about whether this method could truly compress images, so he decided to experiment with various images. The experimental method is as follows:

• First, prepare an image where all pixels are white.
• For $i = 1, \dots, Q$, perform the following operation: "If $T_i = 0$, invert the colors (white to black, black to white) of all $2^N$ pixels in the $X_i$-th row from the top. If $T_i = 1$, invert the colors of all $2^N$ pixels in the $X_i$-th column from the left." That is, if we denote the pixel at the $a$-th row from the top and $b$-th column from the left as $(a, b)$, for each $i$, if $T_i = 0$, perform the operation on pixels $(X_i, b)$ for all $1 \le b \le 2^N$, and if $T_i = 1$, perform the operation on pixels $(a, X_i)$ for all $1 \le a \le 2^N$.
• For each $i$, determine the size of the compressed data when the image after the $i$-th operation is compressed using JOI's method.

To perform as many operations as possible in the experiment, it is necessary to determine the size of the compressed data at high speed.

Task

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

Input

Read the following from standard input:

• The first line contains two integers $N$ and $Q$, separated by a space, representing that the image is of size $2^N \times 2^N$ and that there are $Q$ operations.
• The following $Q$ lines contain the instructions for the operations. The $i$-th line ($1 \le i \le Q$) contains two integers $T_i$ and $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 the $X_i$-th column from the left if $T_i = 1$.

Output

Output $Q$ lines to standard output. The $i$-th line ($1 \le i \le Q$) should contain a single integer representing the size of the compressed data after the $i$-th operation.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [10 points]

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

Subtask 2 [20 points]

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

Subtask 3 [70 points]

• No additional constraints.

Examples

Input 1

2 3
0 1
1 2
0 3

Output 1

13
17
21

Note

In this example, the $Q = 3$ operations are performed as follows:

Initial state: □□□□ □□□□ □□□□ □□□□ ↓ ■■■■ □□□□ □□□□ □□□□ ↓ ■□■■ □■□□ □■□□ □■□□ ↓ ■□■■ □■□□ ■□■■ □■□□