JOI 君好鍾意收集大量圖片，手上已經有好多圖片。最近，JOI 君發現因為收集咗太多圖片，硬碟容量開始唔夠。佢冇錢買新硬碟，但對佢嚟講，刪除自己擁有嘅圖片係最痛苦嘅事，所以佢決定好好壓縮圖片，減少所需容量。

一張圖片由排成正方形嘅 $2^N$ 行、$2^N$ 列，合共 $2^N\times 2^N$ 個像素組成。每個像素唔係白色就係黑色。

JOI 君決定用以下方法壓縮呢類圖片。

• 如果圖片入面所有像素都係同一隻顏色，就只記錄嗰隻顏色。呢個情況下，壓縮後嘅資料大小係 $1$。
• 否則，就將圖片分成 4 張細啲嘅圖片。假設圖片有 $2^k$ 行、$2^k$ 列，就喺縱向同橫向嘅正中間各切開一次，得到 4 張各有 $2^{k-1}$ 行、$2^{k-1}$ 列嘅圖片。用同一方法壓縮呢 4 張細圖片。呢個情況下，壓縮後嘅資料大小定義為 4 張細圖片壓縮後嘅資料大小總和，再加 $1$。

JOI 君開始擔心呢個方法係咪真係可以壓縮圖片，所以決定用唔同嘅圖片做實驗。實驗方法如下。

• 首先準備一張所有像素都係白色嘅圖片。
• 對於 $i=1,\ldots,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$ 行、$2^N$ 列，而操作一共會做 $Q$ 次。
• 接落嚟 $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$ 次操作之後嘅圖片，用 JOI 君嘅方法壓縮後嘅資料大小。

資料範圍

所有輸入資料都符合以下條件。

• $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 2\,048$。

子任務 3 [70 分]

• 冇額外限制。

樣例

輸入格式 1

2 3
0 1
1 2
0 3

輸出格式 1

13
17
21

說明

呢個例子入面，$Q=3$ 次操作會按以下方式進行。

最上面係初始狀態