Matrix Queries

You are given a matrix of size $2n \times 2n$, initially painted white. The color of a cell is either black or white. The price of a matrix is defined as follows:

1. If the matrix is painted with only one color, the price is 1 coin.
2. Otherwise, split the matrix into 4 submatrices of equal size, and the price of the matrix is the sum of the prices of the submatrices plus 1 coin.

You are given $q$ queries. Each query gives the number $x$ of a row or column, and you have to change the color of all cells in this row or column (a white cell becomes black, and a black cell becomes white) and find the price of the new matrix.

The first line contains two integers $n$ and $q$ ($0 \le n \le 20$, $1 \le q \le 10^6$), where $n$ means the matrix has size $2n \times 2n$ and $q$ means the number of queries.

Each of the next $q$ lines contains two integers $t$ and $x$ ($0 \le t \le 1$, $1 \le x \le 2n$). If $t = 0$, the $x$-th row is changed; otherwise, the $x$-th column.

For each query, print the price of the matrix.

In the example, the matrix looks as follows after each query: