题目描述

注意：本题的内存限制不同寻常

序列中的逆序对是指失去自然顺序的元素对，而对于一个 0 到 $(n-1)$ 的排列 $P = [p_0, p_1, \ldots, p_{n-1}]$，其逆序对数是指满足 $i < j$ 且 $p_i > p_j$ 的元素对 $(p_i, p_j)$ 数量。

给定一个排列 $P = [p_0, p_1, \ldots, p_{n-1}]$ 和 $(n-1)$ 次修改 $[(l_1, r_1, d_1), (l_2, r_2, d_2), \ldots, (l_{n-1}, r_{n-1}, d_{n-1})]$，你的任务是确定每次修改前后 $P$ 的逆序对数的奇偶性。

具体来说，排列 $P$ 将有 $n$ 个版本，其中第一个版本如上所述给出，对于 $i = 1, 2, \ldots, n-1$，第 $(i+1)$ 个版本是在第 $i$ 个版本的基础上将下标在 $l_i$ 和 $r_i$ 之间的元素区间循环左移 $d_i$ 次后得到的（更多细节说明请查看样例解释），而你需要为 $P$ 的每个版本计算逆序对数的奇偶性。

此外，由于给定的 $n$ 有点大，我们将通过下面的随机生成器从给定的 $n$、$A$、$B$ 和 $C$ 来生成排列 $P$ 和修改。

随机生成的序列 $[f_0, f_1, \ldots]$ 基于以下定义：

• $\wedge$ 表示按位与，$\oplus$ 表示按位异或，$|x|$ 表示将 $x$ 向下取整到最近的整数；
• 令 $U = 2^{30} - 1$，下面的 $f_x$、$g_x$、$h_x$ 都是介于 $0$ 和 $U$ 之间的整数（闭区间）；
• 令 $f_{-3} = A \land U$，$f_{-2} = B \land U$ 和 $f_{-1} = C \land U$；
• 对于 $i = 0, 1, \ldots$，令 $g_i = f_{i-3} \oplus ((2^{16}f_{i-3}) \land U)$；
• 对于 $i = 0, 1, \ldots$，令 $h_i = g_i \oplus \left\lfloor \frac{g_i}{2^5} \right\rfloor$；
• 对于 $i = 0, 1, \ldots$，令 $f_i = h_i \oplus ((2h_i) \land U) \oplus f_{i-2} \oplus f_{i-1}$。

结合上述生成器，

• $x \mod y$ ($y > 0$) 表示 $x$ 除以 $y$ 的余数；
• 排列 $P$ 从初始状态 $[0, 1, \ldots, n-1]$ 开始，依次交换 $p_i$ 和 $p_{i+(f_i \mod (n-i))}$ ($i = 0, 1, \ldots, n-1$) 后，得到它的第一个版本；
• 对于 $i = 1, \ldots, n-1$，令 $l_i = \min(f_{n+3i-3} \mod n, f_{n+3i-2} \mod n), r_i = \max(f_{n+3i-3} \mod n, f_{n+3i-2} \mod n), d_i = (f_{n+3i-1} \mod n) + 1$。

输入格式

第一行包含一个整数 $T$ ($1 \leq T \leq 10^5$)，表示测试用例的数量。

接下来是 $T$ 个测试用例。对于每个测试用例：

唯一一行包含四个整数 $n$、$A$、$B$ 和 $C$ ($1 \leq n \leq 10^7, 0 \leq A, B, C \leq 10^9$)。

保证 $T$ 个测试用例中 $n$ 之和不超过 $10^7$。

输出格式

对于每个测试用例，在一行中输出一个长度为 $n$ 的字符串，其中第 $i$ 个字符为 0 则表示 $P$ 的第 $i$ 个版本的逆序对数为偶数，为 1 则表示为奇数。

5
3 0 0 0
3 0 0 1
3 0 1 0
3 6 7 8
10 123 456 789

000
111
111
110
1111101111

解释 #1

示例中前两个测试用例生成的序列 $[f_0, f_1, \ldots]$ 为：

• $[0, 0, 0, 0, 0, 0, 0, 0, 0, \ldots]$;
• $[1, 0, 202754, 1, 202755, 692070724, 692070724, 692070725, 792595, \ldots]$.

示例中所有测试用例生成的排列和修改为：

• $P = [0, 1, 2]$, $modifications = [(0, 0, 1), (0, 0, 1)]$;
• $P = [1, 0, 2]$, $modifications = [(0, 1, 2), (1, 2, 2)]$;
• $P = [1, 0, 2]$, $modifications = [(0, 2, 1), (0, 1, 2)]$;
• $P = [2, 1, 0]$, $modifications = [(1, 1, 3), (1, 2, 3)]$;
• $P = [3, 1, 2, 8, 5, 0, 4, 7, 6, 9]$, $modifications = [(1, 8, 2), (0, 6, 10), (3, 5, 10), (2, 4, 2), (7, 8, 9), (1, 2, 7), (0, 9, 2), (8, 9, 2), (5, 7, 5)]$.

对于最后一个测试用例，

• $P$ 的第二个版本为 $[3, 8, 5, 0, 4, 7, 6, 1, 2, 9]$. 是通过将索引区间 $[1, 8]$ 循环左移两次得到的（即 $[\ldots, 1, 2, 8, 5, 0, 4, 7, 6, \ldots] \rightarrow [\ldots, 2, 8, 5, 0, 4, 7, 6, 1, \ldots] \rightarrow [\ldots, 8, 5, 0, 4, 7, 6, 1, 2, \ldots]$）；
• $P$ 的第三个版本为 $[0, 4, 7, 6, 3, 8, 5, 1, 2, 9]$. 是通过将索引区间 $[0, 6]$ 循环左移 $10$ 次得到的（即 $[3, 8, 5, 0, 4, 7, 6, \ldots] \rightarrow [8, 5, 0, 4, 7, 6, 3, \ldots] \rightarrow \cdots \rightarrow [0, 4, 7, 6, 3, 8, 5, \ldots]$）；
• 所有版本的逆序数分别为 $13、21、19、19、21、22、23、25、25$ 和 $27$。