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 翻译