JOI 군은 이미지를 수집하는 것을 아주 좋아하며 많은 이미지를 가지고 있습니다. 최근 JOI 군은 이미지를 너무 많이 수집한 탓에 하드 디스크의 용량이 부족해지고 있음을 깨달았습니다. 새 하드 디스크를 살 여유가 없고, 가지고 있는 이미지를 삭제하는 것도 너무나 괴로운 일이어서, 이미지를 압축하여 용량을 절약하기로 결정했습니다.

이미지는 $2^N$개의 행과 $2^N$개의 열로 이루어진 정사각형 격자에 배열된 총 $2^N \times 2^N$개의 픽셀로 표현됩니다. 각 픽셀은 흰색 또는 검은색입니다.

JOI 군은 이러한 이미지를 다음 방법으로 압축하기로 결정했습니다:

• 만약 이미지의 모든 픽셀이 같은 색이라면, 그 색만 기록합니다. 이 경우 압축된 데이터의 크기는 $1$입니다.
• 그렇지 않다면, 이미지를 네 개의 더 작은 이미지로 나눕니다. 이미지가 $2^k$개의 행과 $2^k$개의 열로 이루어져 있다면, 이미지를 가로와 세로 정중앙에서 나누어 $2^{k-1}$개의 행과 $2^{k-1}$개의 열로 이루어진 네 개의 이미지를 얻습니다. 이 네 개의 더 작은 이미지를 같은 방법으로 압축합니다. 이 경우 압축된 데이터의 크기는 네 개의 더 작은 이미지의 압축된 데이터 크기의 합에 $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 군의 방법으로 압축된 데이터의 크기를 계산하는 프로그램을 작성하십시오.

입력

표준 입력에서 다음을 읽으십시오:

• 첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $Q$가 주어지며, 이는 이미지의 크기가 $2^N \times 2^N$이고 연산이 $Q$번 있음을 나타냅니다.
• 이어지는 $Q$개의 줄에는 연산에 대한 지시가 주어집니다. $i$번째 줄($1 \le i \le Q$)에는 공백으로 구분된 두 정수 $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$번째 연산 후 압축된 데이터의 크기를 나타내는 정수 하나를 출력해야 합니다.

제한

모든 입력 데이터는 다음 조건을 만족합니다:

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

서브태스크

서브태스크 1 [10점]

• $N \le 6$.
• $Q \le 128$.

서브태스크 2 [20점]

• $N \le 10$.
• $Q \le 2048$.

서브태스크 3 [70점]

• 추가적인 제한은 없습니다.

예제

입력 1

2 3
0 1
1 2
0 3

출력 1

13
17
21

노트

이 예에서 $Q = 3$번의 연산은 다음과 같이 수행됩니다:

초기 상태: □□□□ □□□□ □□□□ □□□□ ↓ ■■■■ □□□□ □□□□ □□□□ ↓ ■□■■ □■□□ □■□□ □■□□ ↓ ■□■■ □■□□ ■□■■ □■□□