16332번 - Matrix Queries 다국어

You are given a matrix of size 2ⁿ × 2ⁿ, initially painted in white color. The color of a cell can be either black or white. Let’s define the price of a matrix as:

1. If a matrix is painted with only one color, the price will be 1 coin;
2. Otherwise, you should split the matrix into 4 size-equal matrices, and the price of a matrix will be the sum of submatrices prices plus 1 coin.

You are given q queries. Each query gives you the number of row/column x, and you have to change the color of all cells in this row/column (i.e., if a cell is white, it will be black; if a cell is black, it will be white) and find the price of the new matrix.

The first line contains two integers n and q (0 ≤ n ≤ 20, 1 ≤ q ≤ 10⁶) where n means that the size of the matrix is 2ⁿ × 2ⁿ and q means that there are going to be q queries.

Each of the next q lines contains two integers t and x (0 ≤ t ≤ 1, 1 ≤ x ≤ 2ⁿ). If t = 0, then the x-th row will be changed; otherwise, the x-th column.

For each query, print a matrix price.

In the sample, after each query the matrix will be as follows: