시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 2 2 2 100.000%

문제

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

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

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

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

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

  • まずすべての画素が白であるような画像を用意する.
  • i = 1, · · · , Q について,「Ti = 0 ならば上から数えて Xi 行目の 2N 個の画素,Ti = 1 ならば左から数え て Xi 列目の 2N 個の画素の,白黒をそれぞれ反転させる」という操作を行う.すなわち,上から a 行 目で左から b 列目にあるカードを (a, b) と書いたとき,各 i について,Ti = 0 ならば 1 ≤ b ≤ 2N をみ たす画素 (Xi, b) に,Ti = 1 ならば 1 ≤ a ≤ 2N をみたす画素 (a, Xi) に対し,画素が白ならば黒に,黒 ならば白に変える操作を行う.
  • 各 i について,i 回目の操作が終わったあとの画像を JOI 君の方法で圧縮したときの,圧縮後のデー タの大きさを調べる.

実験では操作をできるだけ多く行うために,圧縮後のデータの大きさを高速に調べる必要がある.

画像の大きさを表す整数 N,操作の回数 Q および Q 回の操作の指示が与えられたとき,それぞれの操作 が終わった後の画像を JOI 君の方法で圧縮したときの,圧縮後のデータの大きさを求めるプログラムを作 成せよ.

입력

標準入力から以下の入力を読み込め.

  • 1 行目には 2 つの整数 N, Q が空白を区切りとして書かれており,画像が 2N 行 2N 列の大きさである ことと,操作を行う回数が Q 回であることを表す.
  • 続く Q 行には操作の指示が書かれている.Q 行のうちの i 行目 (1 ≤ i ≤ Q) には 2 つの整数 Ti, Xi (0 ≤ Ti ≤ 1 かつ 1 ≤ Xi ≤ 2N) が空白を区切りとして書かれており,i 回目の操作は Ti = 0 なら上から Xi 行目,Ti = 1 なら左から Xi 列目の画素の白黒を全て反転することを表す.

출력

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

제한

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

예제 입력 1

2 3
0 1
1 2
0 3

예제 출력 1

13
17
21

この例では,Q = 3 回の操作は以下のように行われる.

初期状態