题目描述

JOI 君非常喜欢收集大量图片，并拥有许多图像。最近，JOI 君发现自己因收集过多图片而导致硬盘容量略显不足。他没有购买新硬盘的预算，但删除已有的图片对他而言是极大的痛苦，因此他决定通过巧妙地压缩图片来减少存储空间。

每张图片由 $2^N$ 行 $2^N$ 列的正方形像素网格表示，共计 $2^N \times 2^N$ 个像素。每个像素为白色或黑色。

JOI 君采用以下方法对这类图像进行压缩：

• 若图像内所有像素颜色相同，则仅记录该颜色。此时压缩后数据的大小为 $1$。
• 否则，将图像分割为四个较小的子图像。若原图像为 $2^k$ 行 $2^k$ 列，则沿纵向和横向的中心线进行分割，得到四个 $2^{k-1}$ 行 $2^{k-1}$ 列的子图像。对这些较小的子图像递归应用相同的压缩方法。此时，压缩后数据的大小为四个子图像压缩后数据大小之和再加 $1$。

JOI 君对这种方法是否能有效压缩图像感到不安，因此决定对多种图像进行实验。实验方法如下：

• 首先准备一张所有像素均为白色的图像。
• 对于 $i = 1, \cdots, Q$，执行以下操作：若 $T_i = 0$，则反转从上数第 $X_i$ 行的 $2^N$ 个像素的颜色；若 $T_i = 1$，则反转从左数第 $X_i$ 列的 $2^N$ 个像素的颜色。即，记从上第 $a$ 行、从左第 $b$ 列的像素为 $(a,b)$，对于每个 $i$，当 $T_i = 0$ 时，对满足 $1 \leq b \leq 2^N$ 的像素 $(X_i,b)$ 执行颜色反转（白变黑，黑变白）；当 $T_i = 1$ 时，对满足 $1 \leq a \leq 2^N$ 的像素 $(a,X_i)$ 执行颜色反转。
• 对于每个 $i$，在第 $i$ 次操作结束后，调查按 JOI 君方法压缩该图像后所得数据的大小。

为了在实验中执行尽可能多的操作，需要高效计算压缩后数据的大小。

任务

给定表示图像大小的整数 $N$、操作次数 $Q$ 以及 $Q$ 次操作的描述，编写程序计算每次操作结束后，按 JOI 君方法压缩图像所得数据的大小。

输入格式

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

• 第 $1$ 行包含两个以空格分隔的整数 $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

提示

样例 1 解释

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

:::align{center} :::

限制

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

• $1 \leq N \leq 20$
• $1 \leq Q \leq 2\,000\,000$

子任务

子任务 1 [10 分]

满足以下条件：

• $N \leq 6$
• $Q \leq 128$

子任务 2 [20 分]

满足以下条件：

• $N \leq 10$
• $Q \leq 2\,048$

子任务 3 [70 分]

无额外限制。

翻译由 DeepSeek V3 完成