AT_abc417_g.[ABC417G] Binary Cat

定义字符串 $S_0,S_1$，其中 $S_0=$ 0，$S_1=$ 1。

给定 $Q$ 个查询，请依次处理每个查询。
对于第 $i$ 个查询 $(1\leq i\leq Q)$，给出三个整数 $(L_i,R_i,X_i)$。

将 $S_{L_i}$ 和 $S_{R_i}$ 按顺序连接，得到字符串 $S_{i+1}$。然后，求出 $S_{i+1}$ 的第 $X_i$ 个字符。

保证 $X_i$ 不会超过 $S_{i+1}$ 的长度。

输入以如下格式从标准输入给出。

$Q$
$L_1$ $R_1$ $X_1$
$L_2$ $R_2$ $X_2$
$\vdots$
$L_Q$ $R_Q$ $X_Q$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

限制条件

• $1\leq Q\leq 5\times 10^5$
• $0\leq L_i,R_i\leq i$
• $1\leq X_i\leq 10^{18}$
• $X_i$ 不会超过 $S_{i+1}$ 的长度
• 所有输入均为整数

样例解释 1

每个查询的处理如下：

• 第 1 个查询，将 $S_0=$0 和 $S_1=$1 连接，得到 $S_2=$01。$S_2$ 的第 1 个字符是 0，因此第 1 行输出 $0$。
• 第 2 个查询，将 $S_0=$0 和 $S_0=$0 连接，得到 $S_3=$00。$S_3$ 的第 2 个字符是 0，因此第 2 行输出 $0$。
• 第 3 个查询，将 $S_1=$1 和 $S_1=$1 连接，得到 $S_4=$11。$S_4$ 的第 1 个字符是 1，因此第 3 行输出 $1$。
• 第 4 个查询，将 $S_2=$01 和 $S_3=$00 连接，得到 $S_5=$0100。$S_5$ 的第 2 个字符是 1，因此第 4 行输出 $1$。
• 第 5 个查询，将 $S_2=$01 和 $S_4=$11 连接，得到 $S_6=$0111。$S_6$ 的第 3 个字符是 1，因此第 5 行输出 $1$。
• 第 6 个查询，将 $S_5=$0100 和 $S_4=$11 连接，得到 $S_7=$010011。$S_7$ 的第 2 个字符是 1，因此第 6 行输出 $1$。
• 第 7 个查询，将 $S_6=$0111 和 $S_7=$010011 连接，得到 $S_8=$0111010011。$S_8$ 的第 6 个字符是 1，因此第 7 行输出 $1$。

由 ChatGPT 4.1 翻译