P5523 [yLOI2019] 珍珠

> 别叹息太多告别，至少相遇很真切。 > 摇曳着盛放枯竭，时间从未停歇。 > 天涯浪迹的白雪，念念不忘山川蝴蝶。 > 听说有人孤负黑夜，偏要点亮人间的月。 ——银临《珍珠》

扶苏给了你一个放珍珠的小匣子，这个匣子在左右两端都可以无限制的加入珍珠，珍珠在匣子里会排成一列，每次在左端加入珍珠，这个珍珠会被加入到这个珍珠序列的最左侧，在右端加入则会被加入到珍珠序列的最右侧。初始时，匣子是空的。 这些珍珠要么是黑色的，要么是白色的，为了方便起见，我们将白色看作 $0$，黑色看作 $1$。 在人鱼的世界中，定义颜色 $A$ **组合** 颜色 $B$ 为 $A\operatorname{nand}B$，读作 $A$ 与非 $B$。 定义 $A \operatorname{nand} B = \operatorname{not} (A \operatorname{and}B)$ ，其中 $\operatorname{and}$ 运算代表二进制与运算，$\operatorname{not}$ 运算代表二进制非运算。 定义位置 $x$ 到位置 $y$ 的组合和为： 从 $x$ 开始向 $y$ ，第一个颜色组合第二个颜色的结果组合第三个颜色，得到的结果组合第四个颜色……一直组合到位置 $y$ 的颜色的结果。特别的，$x = y$ 时，组合和为该颜色。 形式化的，设 $C_{x, y}$ 为序列 $A$ 从 $x$ 到 $y$ 的组合和，则 $$C_{x, y} = \begin{cases} C_{x, y - 1} \operatorname{nand} A_y & x < y \\ C_{x, y + 1} \operatorname{nand} A_y & x > y \\ A_x &x = y \end{cases}$$ 例如，给定序列 $1, 1, 0, 0$，从 $2$ 到 $4$ 的组合和为 $$(1 \operatorname{nand} 0) \operatorname{nand} 0 = 1 \operatorname{nand} 0 = 1$$ 从 $3$ 到 $1$ 的组合和为 $$(0 \operatorname{nand} 1) \operatorname{nand} 1 = 1 \operatorname{nand} 1 = 0$$ 从 $2$ 到 $2$ 的组合和为 $$1$$ 扶苏会在匣子的两边加入一些珍珠，或者给定一个位置 $p$，询问你从左向右数第 $1$ 个位置到从左向右数第 $p$ 个位置的组合和，或者从右向左数第 $1$ 个位置到从右向左数第 $p$ 个位置的组合和。

无

无

#### 样例输入输出 1 解释 第一次操作，$x=0,y=1,z=0$，在匣子右端插入一个 $0$，那么匣子里的珍珠序列为 $\{0\}$ 第二次操作，$x = 1,y = 0,z = 1$，查询从左向右数第一个数到第一个数的组合和，答案是 $0$。 第三次操作，$x = 0,y = 1,z = 1$，在匣子右端插入一个 $1$，匣子里的珍珠序列为 $\{0,~1\}$ 第四次操作，$x = 1,y = 0,z = 1$，查询从左向右数第一个数到第一个数的组合和，答案是 $0$。 第五次操作，$x = 0,y = 0,z = 0$，在匣子左侧插入一个 $0$，那么匣子里的珍珠序列为 $\{0,~0,~1\}$ 第六次操作，$x = 0,y = 1,z = 1$，在匣子右侧插入一个 $1$，那么匣子的珍珠序列为 $\{0,~0,~1,~1\}$ 没有任何一次查询的结果满足【输出格式】中提到的任意一种情况，于是输出 ``0 0 0 0``。 --- #### 数据规模与约定 **本题采用多测试点捆绑测试，共有 $7$ 个子任务**。 - Subtask 1（5 points）：$n = m = 0$。 - Subtask 2（15 points）：$n = 1001$。 - Subtask 3（15 points）：$n = 10^5 + 2$。 - Subtask 4（10 points）：$n = 10^7 + 3$，对于所有 $x = 0$ 的操作，保证 $z = 1$。 - Subtask 5（10 points）：$n = 10^7 + 4$，对于所有 $x = 0$ 的操作，保证 $z = 0$。 - Subtask 6（15 points）：$n = 10^7 + 5$，$m = 0$。 - Subtask 7（30 points）：$n = 10^7 + 6$。 对于全部的测试点，保证 $0 \leq n \leq 10^7 + 6$，$0 \leq m \leq \min(n, 10^6)$，$x, y \in \{0, 1\}$，且对于所有 $x = 0$ 的操作，保证 $z \in \{0, 1\}$，若设 $k$ 为在任一查询时匣子里的珍珠个数，则保证对于 $x = 1$ 的操作，$1 \leq z \leq k$，匣子为空时不会有查询操作。 --- #### 提示与说明 - 请注意常数因子对程序效率造成的影响。 - $n$ 的末位数字可以帮助你快速的判断测试点所属的子任务。 - 由于涉及到非操作，与非运算可能不具备一些常见位运算的运算律，请格外注意。 - std 使用 C++ 语言，保证时限是 std 用时的 1.5 倍以上，**但是不保证其他语言能够通过本题**。 - 对于 C++ 选手，如果你直接复制上面的生成器，保证生成器运行总时间不超过 300ms。