[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$ 个位置的组合和。

每个输入文件中都有且仅有一组测试数据。 数据的第一行是一个整数 $n$，代表扶苏的操作个数。 由于正常读入每个操作所需要的输入量过大，因此我们采用下面的生成器来生成每个操作。 ```cpp #include <cstdio> namespace Maker { typedef unsigned int uit; bool __sp; uit __x, __y, __z; int __type, __k, __m; template <typename T> inline void qr(T &x) { char ch = getchar(), lst = ' '; while ((ch > '9') || (ch < '0')) lst = ch, ch = getchar(); while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); if (lst == '-') x = -x; } template <typename T> inline void Begin(const T &x) { __type = x % 10; qr(__x); qr(__y); qr(__z); qr(__m); __sp = (__type == 3) || (__type == 4); __type &= 1; } inline uit __Next_Integer() { __x ^= __y << (__z & 31); __y ^= __z >> (__x & 31); __z ^= __x << (__y & 31); __x ^= __x >> 5; __y ^= __y << 13; __z ^= __z >> 6; return __x; } inline uit Rand() { return __Next_Integer(); } template <typename Tx, typename Ty, typename Tz> inline void Get_Nextline(Tx &x, Ty &y, Tz &z) { if (__m) { --__m; x = 0; y = 0; z = 0; qr(x); qr(y); qr(z); if (x == 0) { ++__k; } } else { x = Rand() & 1; y = Rand() & 1; if (__k == 0) { x = 0; } if (x == 0) { ++__k; if (__sp) { z = __type; } else { z = Rand() & 1; } } else { int dk = __k >> 1; if (dk == 0) { z = 1; } else { z = Rand() % dk + dk; } } } } } ``` 对于 C/C++ 选手，我们提供了如上的数据生成代码（C 选手请使用 C++ 语言提交)，请将他们直接复制到你的代码中。 对于非 C/C++ 选手，请你自行按照上面代码的内容，自行写出你所使用语言的对应生成器。 下面的内容只针对 C++ 选手，请其他语言的选手自行按照对应语言的语法来完成代码。 在读入 $n$ 这个数字以后，请你调用 ``Maker`` 命名空间中的 ``Begin`` 函数，函数的参数为 $n$。换句话说，你的代码中需要出现类似 ``Maker::Begin(n)`` 的语句。 在调用完 ``Maker::Begin`` 函数以后，生成器就可以开始工作了。一共有 $n$ 次操作，每次操作时请你调用 ``Maker::Get_Nextline`` 函数，传入三个**整形**变量，(不妨设为 $x,y,z$)，每次函数调用结束以后，$x,y,z$ 的值都会被修改，作为每次操作的参数。具体含义如下： > 每次操作会有三个整数作为参数， 依次记为 $x,y,z$ > > - 如果 $x = 0$，则代表这是一次插入操作； > - 如果 $x = 1$，则代表这是一次查询。 > - 如果 $y = 0$，则代表插入操作是从左侧进行的，或者查询的位置是从左向右数的； > - 如果 $y = 1$，则代表插入操作是从右侧进行的，或者查询的位置是从右向左数的。 > - 如果 $x = 0$，则 $z$ 是一个非零即一的整数，代表插入珍珠的颜色，$0$ 代表白色，$1$ 代表黑色； > - 如果 $x = 1$，则 $z$ 代表查询从第一个到第 $z$ 个位置的组合和。组合和的方向和位置的方向由参数 $y$ 决定。 对于 C/C++ 选手，我们提供了模板程序([模板程序链接](https://www.luogu.org/paste/lk7wn4a1))，在这个程序中，已经做好了变量的读入和生成器的初始化，同时能够自动获取 $x,y,z$ 的值，你需要做的只是每次依照题意进行一个操作，最终输出答案。你可以自主选择是否使用这个模板，最终的评测得分与你的代码内容**无关**。 **特别提醒：不建议使用 ``fread`` 等直接从输入中大量读取信息然后保存的函数对 $n$ 进行读入，如果你非要这么做，请你自行重写 ``Maker::Begin()`` 中的读入部分。** **从输入数据的第二行起，所有的数据都会被生成器自动读入（包括第二行），不需要你再行读入**。 输入数据的第二行是四个整数 $a,b,c,m$，其中 $a,b,c$ 是生成器的参数，$m$ 为需要额外读入的操作数。 为了在某种意义上避免因为生成的操作完全随机而产生的乱搞做法，我们将首先额外读入 $m$ 个给定的操作，然后再行随机。 以下 $m$ 行，每行三个整数 $x,~y,~z$，代表一次操作。 请特别注意，这 $m$ 次操作会被生成器**自动读入**。

为了避免输出过大，请输出一行四个用空格隔开的整数，分别代表所有的查询中： - 一共有多少次查询的结果为 $1$。 - 一共有多少次查询的操作编号为奇数且查询结果为 $0$。 - 一共有多少次查询的操作编号为偶数且查询结果为 $1$。 - 一共有多少次查询的操作编号是 $1024$ 的倍数且查询结果为 $0$。 定义第 $i$ 次操作的操作编号为 $i$。 **注意，一次插入也算做一次操作**。

6
233 666 250 0

0 0 0 0

#### 样例输入输出 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。