|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1.5 초||512 MB||66||29||22||46.809%|
You are given a matrix of size 2n × 2n, 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:
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 ≤ 106) where n means that the size of the matrix is 2n × 2n 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 ≤ 2n). If t = 0, then the x-th row will be changed; otherwise, the x-th column.
For each query, print a matrix price.
2 7 1 3 0 2 1 1 1 4 0 4 0 3 1 1
13 17 21 17 21 17 13
In the sample, after each query the matrix will be as follows: