이미지 수집은 즐거워

JOI 군은 이미지를 많이 모으는 것을 아주 좋아해서 많은 이미지를 가지고 있다. 최근 JOI 군은 이미지를 너무 많이 모은 탓에 하드 디스크의 용량이 부족해지고 있다는 것을 알아차렸다. 새 하드 디스크를 살 돈은 없지만, JOI 군에게 가지고 있는 이미지를 삭제하는 것은 이 이상 없는 고통이므로, 이미지를 잘 압축해서 용량을 줄이기로 했다.

이미지는 세로 $2^N$행, 가로 $2^N$열의 정사각형 모양으로 늘어선 총 $2^N \times 2^N$개의 화소로 나타낸다. 각 화소는 흰색이나 검은색 중 하나이다.

이런 이미지를 JOI 군은 다음과 같은 방법으로 압축하기로 했다.

• 이미지 안의 화소가 모두 같은 색이면, 그 색만 기록한다. 이때 압축 후 데이터의 크기는 1이다.
• 그렇지 않으면, 이미지를 4개의 더 작은 이미지로 나눈다. 이미지가 세로 $2^k$행, 가로 $2^k$열이라고 하면, 세로와 가로 각각 중심에서 이미지를 분할하여 세로 $2^{k-1}$행, 가로 $2^{k-1}$열의 이미지 4개를 얻는다. 이 4개의 작아진 이미지를 같은 방법으로 압축한다. 이때 압축 후 데이터의 크기는 4개의 작은 이미지의 압축 후 데이터 크기의 합에 1을 더한 것으로 한다.

JOI 군은 이 방법으로 정말 이미지가 압축되는지 불안해졌기 때문에, 여러 가지 이미지에 대해 실험을 해 보기로 했다. 실험 방법은 다음과 같다.

• 먼저 모든 화소가 흰색인 이미지를 준비한다.
• $i = 1, \dots, Q$에 대해, "$T_i = 0$이면 위에서 세어 $X_i$번째 행의 $2^N$개 화소, $T_i = 1$이면 왼쪽에서 세어 $X_i$번째 열의 $2^N$개 화소의 흑백을 각각 반전시킨다"는 조작을 한다. 즉, 위에서 $a$행이고 왼쪽에서 $b$열인 화소를 $(a, b)$라고 쓸 때, 각 $i$에 대해 $T_i = 0$이면 $1 \le b \le 2^N$을 만족하는 화소 $(X_i, b)$에, $T_i = 1$이면 $1 \le a \le 2^N$을 만족하는 화소 $(a, X_i)$에 대해, 화소가 흰색이면 검은색으로, 검은색이면 흰색으로 바꾸는 조작을 한다.
• 각 $i$에 대해, $i$번째 조작이 끝난 뒤의 이미지를 JOI 군의 방법으로 압축했을 때의 압축 후 데이터의 크기를 조사한다.

실험에서는 조작을 가능한 한 많이 하기 위해, 압축 후 데이터의 크기를 빠르게 조사할 필요가 있다.

이미지의 크기를 나타내는 정수 $N$, 조작의 횟수 $Q$ 및 $Q$번의 조작 지시가 주어졌을 때, 각 조작이 끝난 뒤의 이미지를 JOI 군의 방법으로 압축했을 때의 압축 후 데이터의 크기를 구하는 프로그램을 작성하시오.

표준 입력에서 다음 입력을 읽는다.

• 1번째 줄에는 2개의 정수 $N, Q$가 공백을 구분으로 쓰여 있으며, 이미지가 $2^N$행 $2^N$열의 크기라는 것과 조작을 하는 횟수가 $Q$번이라는 것을 나타낸다.
• 이어지는 $Q$번째 줄에는 조작 지시가 쓰여 있다. $Q$번째 줄 중 $i$번째 줄 ($1 \le i \le Q$)에는 2개의 정수 $T_i, X_i$ ($0 \le T_i \le 1$ 그리고 $1 \le X_i \le 2^N$)가 공백을 구분으로 쓰여 있으며, $i$번째 조작은 $T_i = 0$이면 위에서 $X_i$번째 행, $T_i = 1$이면 왼쪽에서 $X_i$번째 열의 화소 흑백을 모두 반전시키는 것을 나타낸다.

표준 출력에 $Q$행 출력한다. $i$행째 ($1 \le i \le Q$)에는 $i$번째 조작이 끝난 뒤의 이미지를 JOI 군의 방법으로 압축했을 때의 압축 후 데이터의 크기를 나타내는 정수 1개를 출력한다.

• $1 \le N \le 20$.
• $1 \le Q \le 2\,000\,000$.