题目背景

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

——银临《珍珠》

题目描述

扶苏给了你一个放珍珠的小匣子，这个匣子在左右两端都可以无限制的加入珍珠，珍珠在匣子里会排成一列，每次在左端加入珍珠，这个珍珠会被加入到这个珍珠序列的最左侧，在右端加入则会被加入到珍珠序列的最右侧。初始时，匣子是空的。

这些珍珠要么是黑色的，要么是白色的，为了方便起见，我们将白色看作 $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$，代表扶苏的操作个数。

由于正常读入每个操作所需要的输入量过大，因此我们采用下面的生成器来生成每个操作。

#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++ 选手，我们提供了模板程序(模板程序链接)，在这个程序中，已经做好了变量的读入和生成器的初始化，同时能够自动获取 $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。