收集图片很有趣 - المسألة

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, \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 君的方法压缩图片时，压缩后的数据大小。

从标准输入读取以下内容：

第 $1$ 行包含两个整数 $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$ 次操作完成后，使用 JOI 君的方法压缩图片时，压缩后的数据大小。

所有输入数据满足以下条件：

13
17
21

在此例中，$Q = 3$ 次操作执行过程如下：

初始状态 □□□□ □□□□ □□□□ □□□□ ↓ ■■■■ □□□□ □□□□ □□□□ ↓ ■□■■ □■□□ □■□□ □■□□ ↓ ■□■■ □■□□ ■□■■ □■□□

QOJ.ac