행렬 쿼리

크기가 $2n \times 2n$인 행렬이 주어지고, 처음에는 모든 칸이 흰색이다. 각 칸의 색은 검은색 또는 흰색이다. 행렬의 가격을 다음과 같이 정의하자.

1. 행렬이 한 가지 색으로만 칠해져 있으면 가격은 1코인이다.
2. 그렇지 않으면 행렬을 크기가 같은 4개의 부분 행렬로 나누고, 행렬의 가격은 부분 행렬들의 가격의 합에 1코인을 더한 값이다.

$q$개의 쿼리가 주어진다. 각 쿼리는 행/열의 번호 $x$를 주고, 이 행/열에 있는 모든 칸의 색을 바꾸고(흰색 칸은 검은색이 되고, 검은색 칸은 흰색이 된다) 새 행렬의 가격을 구해야 한다.

첫째 줄에 두 정수 $n$과 $q$가 주어진다. ($0 \le n \le 20$, $1 \le q \le 10^6$) $n$은 행렬의 크기가 $2n \times 2n$임을, $q$는 쿼리의 개수를 의미한다.

다음 $q$개의 줄에는 각각 두 정수 $t$와 $x$가 주어진다. ($0 \le t \le 1$, $1 \le x \le 2n$) $t = 0$이면 $x$번째 행을 바꾸고, 그렇지 않으면 $x$번째 열을 바꾼다.

각 쿼리마다 행렬의 가격을 출력한다.

예시에서 각 쿼리를 처리한 후 행렬은 다음과 같다.