JOI-kun likes to collect images and has collected many images. Recently, he has been collecting too many images and noticed, to his dismay, that his hard disk is running out of space. Unfortunately, he doesn't have enough savings to buy a new hard disk. It pains JOI-kun to delete any of the images he has painstakingly collected, so he has decided to use compression to minimize the space requirements of his image collection.
Each image consists of 2N rows and 2N columns of pixels for a total of 2N × 2N pixels. Each pixel has one of two colours: black or white.
JOI-kun has decided to compress his images with the following method:
- If the pixels within an image consist entirely of pixels of the same colour, JOI-kun records the colour of the pixel. The compressed size of such an image is 1.
- If the pixels within an image are not all of the same colour, then JOI-kun divides the image into four sub-images. For an image of size 2k × 2k, the centre of the image divides the image into four sub-images of size 2k-1 × 2k-1. The four sub-images are then compressed in the same manner. The compressed size of such an image is the sum of the compressed sizes of the four sub images + 1.
JOI-kun is unsure if this compression scheme is able to compress his images safely, so he decided to test this compression scheme before using it on all of his images. The testing is done in the following manner:
- The test begins with an all-white image.
-
For i = 1, …, Q, an operation is performed using two integers Ti and Xi.
- If Ti = 0, the colours of the pixels on the Xith row of the image are flipped. In other words, denoting a pixel on the ath row from the top and bth column from the left by (a, b), all pixels (Xi, b) for 1 ≤ b ≤ 2N are flipped.
- If Ti = 1, the colours of the pixels on the Xith column of the image are flipped. In other words, all pixels (a, Xi) for 1 ≤ a ≤ 2N are flipped.
When a pixel is flipped, it becomes black if it was initially white and white if it was initially black.
- After each operation, the compressed size of the resulting image is recorded.
JOI-kun would like to test the compression scheme thoroughly with many operations, so he needs to be able to determine the compressed size of the image after each operation as quickly as possible.
Given the size of the image N and the Q operations JOI-kun will use to test the compression scheme, find the compressed size of the resulting image after each operation.
Input
Read from standard input.
- On the first line, there are two integers, N and Q. This means that the image is of size 2N × 2N and Q operations will be performed on it.
- On the ith line of the next Q lines, there are two integers, Ti and Xi (0 ≤ Ti ≤ 1 and 1 ≤ Xi ≤ 2N). If Ti = 0, this means that the ith operation flips the Xith row of the image, otherwise if Ti = 1, then the operation flips the Xith column of the image.
Output
Print to standard output. For each operation in the given order, print one integer on one line, representing the compressed size of the resulting image using JOI-kun's compression scheme.
Constraints
All test cases satisfy the following constraints.
- 1 ≤ N ≤ 20.
- 1 ≤ Q ≤ 2 000 000.
Subtasks
Subtask 1 (10 points):
The following constraints are satisfied.
Subtask 2 (20 points):
The following constraints are satisfied.
Subtask 3 (70 points):
No further constraints.
Sample Input
2 3
0 1
1 2
0 3
Sample Output
13
17
21
Explanation
In this test case, the state of the image before and after each of the Q = 3 operations is as follows:
| Initial state: |
|
After operation 1: |
|
After operation 2: |
|
After operation 3: |
|
→ |
|
→ |
|
→ |
|