JOIkun 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 JOIkun 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 2^{N} rows and 2^{N} columns of pixels for a total of 2^{N} × 2^{N} pixels. Each pixel has one of two colours: black or white.
JOIkun has decided to compress his images with the following method:
 If the pixels within an image consist entirely of pixels of the same colour, JOIkun 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 JOIkun divides the image into four subimages. For an image of size 2^{k} × 2^{k}, the centre of the image divides the image into four subimages of size 2^{k1} × 2^{k1}. The four subimages 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.
JOIkun 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 allwhite image.

For i = 1, …, Q, an operation is performed using two integers T_{i} and X_{i}.
 If T_{i} = 0, the colours of the pixels on the X_{i}^{th} row of the image are flipped. In other words, denoting a pixel on the a^{th} row from the top and b^{th} column from the left by (a, b), all pixels (X_{i}, b) for 1 ≤ b ≤ 2^{N} are flipped.
 If T_{i} = 1, the colours of the pixels on the X_{i}^{th} column of the image are flipped. In other words, all pixels (a, X_{i}) for 1 ≤ a ≤ 2^{N} 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.
JOIkun 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 JOIkun 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 2^{N} × 2^{N} and Q operations will be performed on it.
 On the ith line of the next Q lines, there are two integers, T_{i} and X_{i} (0 ≤ T_{i} ≤ 1 and 1 ≤ X_{i} ≤ 2^{N}). If T_{i} = 0, this means that the ith operation flips the X_{i}^{th} row of the image, otherwise if T_{i} = 1, then the operation flips the X_{i}^{th} 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 JOIkun'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: 

→ 

→ 

→ 
