[AdditionalFile5112.zip](file://AdditionalFile5112.zip?type=additional_file)

#5112. 「JOISC 2013 Day1」欢乐图像收集

标签: 传统 | 时间限制: 5000 ms | 内存限制: 256 MiB |

题目描述

题目译自 JOISC 2013 Day1 T2 「たのしい画像収集」

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, \cdots, Q$，执行以下操作：如果 $T_{i}=0$，则将上数第 $X_{i}$ 行的所有 $2^{N}$ 个像素的颜色反转（白变黑，黑变白）； اگر $T_{i}=1$，则将左数第 $X_{i}$ 列的所有 $2^{N}$ 个像素的颜色反转。具体来说，若用 $(a, b)$ 表示第 $a$ 行第 $b$ 列的像素，则当 $T_{i}=0$ 时，反转所有满足 $1 \leq b \leq 2^{N}$ 的像素 $(X_{i}, b)$ 的颜色；当 $T_{i}=1$ 时，反转所有满足 $1 \leq a \leq 2^{N}$ 的像素 $(a, X_{i})$ 的颜色。
• 在每次操作完成后，计算按照 JOI 君的方法压缩当前图像后，数据的大小。

为了在实验中尽可能多地执行操作，你需要设计一个程序，快速计算每次操作后的压缩数据大小。

给定表示图像大小的整数 $N$、操作次数 $Q$ 以及 $Q$ 次操作的具体指令，你需要编写程序，计算每次操作完成后，按照 JOI 君的方法压缩图像时，压缩后的数据大小。

输入格式

从标准输入中读取以下数据：

• 第一行包含两个整数 $N, Q$，用空格分隔，表示图像为 $2^{N}$ 行 $2^{N}$ 列的大小，且操作次数为 $Q$ 次。
• 接下来 $Q$ 行，每行描述一次操作。其中第 $i$ $(1 \leq i \leq Q)$ 行包含两个整数 $T_{i}, X_{i}$ $(0 \leq T_{i} \leq 1, 1 \leq X_{i} \leq 2^{N})$，用空格分隔，表示第 $i$ 次操作：若 $T_{i}=0$，则反转上数第 $X_{i}$ 行的所有像素颜色；若 $T_{i}=1$，则反转左数第 $X_{i}$ 列的所有像素颜色。

输出格式

在标准输出中输出 $Q$ 行，第 $i$ $(1 \leq i \leq Q)$ 行输出一个整数，表示第 $i$ 次操作完成后，按照 JOI 君方法压缩图像后的数据大小。

样例

输入

2 3
0 1
1 2
0 3

输出

13
17
21

在这个例子中，$Q=3$ 次操作按以下方式进行：

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 20$
• $1 \leq Q \leq 2000000$

详细子任务附加限制及分值如下表所示。