17743번 - Collecting Images is Fun 서브태스크다국어

JOI 君は画像をたくさん集めることが大好きで，多くの画像を持っている．最近になって JOI 君は，画 像を集めすぎてしまったせいでハードディスクの容量が不足気味になっていることに気がついた．新しく ハードディスクを購入するお金はないが，JOI 君にとって持っている画像を削除することはこの上ない苦 痛であるため，画像をうまく圧縮して容量を削減することにした．

画像は縦 2^N 行，横 2^N 列の正方形状に並んだ合計 2^N × 2^N 個の画素で表される．それぞれの画素は白か 黒のいずれかである．

このような画像を JOI 君は次の方法で圧縮することにした．

• 画像内の画素がすべて同じ色ならば，その色だけを記録する．このとき圧縮後のデータの大きさは 1 である．
• そうでなければ，画像を 4 つのより小さな画像に分ける．画像が縦 2^k 行，横 2^k 列であるとすると， 縦と横それぞれ中心で画像を分割し，縦 2^k−1 行，横 2^k−1 列の画像 4 つを得る．これら 4 つの小さく なった画像を同じ方法で圧縮する．このとき圧縮後のデータの大きさは，4 つの小さい画像の圧縮後 のデータの大きさの和に，さらに 1 を加えたものであるとする．

JOI 君はこの方法で本当に画像が圧縮できるのか不安になったため，さまざまな画像に対して実験をし てみることにした．実験の方法は次のようなものである．

• まずすべての画素が白であるような画像を用意する．
• i = 1, · · · , Q について，「T_i = 0 ならば上から数えて X_i 行目の 2^N 個の画素，T_i = 1 ならば左から数え て X_i 列目の 2^N 個の画素の，白黒をそれぞれ反転させる」という操作を行う．すなわち，上から a 行 目で左から b 列目にあるカードを (a, b) と書いたとき，各 i について，T_i = 0 ならば 1 ≤ b ≤ 2^N をみ たす画素 (X_i, b) に，T_i = 1 ならば 1 ≤ a ≤ 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 ≤ i ≤ Q) には 2 つの整数 T_i, X_i (0 ≤ T_i ≤ 1 かつ 1 ≤ Xi ≤ 2^N) が空白を区切りとして書かれており，i 回目の操作は T_i = 0 なら上から X_i 行目，T_i = 1 なら左から Xi 列目の画素の白黒を全て反転することを表す．

標準出力に Q 行出力せよ．i 行目 (1 5 i 5 Q) には，i 回目の操作が終わった後の画像を JOI 君の方法で 圧縮したときの，圧縮後のデータの大きさを表す 1 つの整数を出力せよ．

• 1 ≤ N ≤ 20.
• 1 ≤ Q ≤ 2 000 000.

• N ≤ 6.
• Q ≤ 128.

• N ≤ 10.
• Q ≤ 2 048.

追加の制限はない．