较小的和

题目描述

给定长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$。

回答以下 $Q$ 个查询。第 $i$ 个查询如下：

在 $A_{L_i},A_{L_i+1},\dots,A_{R_i}$ 中，求不超过 $X_i$ 的元素之和。

这里，你需要在线回答这些查询。

也就是说，只有回答完当前查询后，下一个查询才会被给出。

因此，第 $i$ 个查询本身不直接给出，而是给出加密后的输入 $\alpha_i, \beta_i, \gamma_i$。请按以下步骤还原原始查询并回答它。

设 $B_0=0$，$B_i$ 为第 $i$ 个查询的答案。

查询可按如下方式解密：

• $L_i = \alpha_i \oplus B_{i-1}$
• $R_i = \beta_i \oplus B_{i-1}$
• $X_i = \gamma_i \oplus B_{i-1}$

其中，$x \oplus y$ 表示 $x$ 和 $y$ 的按位异或。

什么是按位异或？

非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下：

在二进制表示下，$A \oplus B$ 的 $2^k$ 位（$k \ge 0$）上的数字为：如果 $A$ 和 $B$ 中恰好一个在该位上的数字为 $1$，则为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制下 $011 \oplus 101 = 110$）。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$Q$
$\alpha_1$ $\beta_1$ $\gamma_1$
$\alpha_2$ $\beta_2$ $\gamma_2$
$\vdots$
$\alpha_Q$ $\beta_Q$ $\gamma_Q$

输出格式

输出 $Q$ 行。

第 $i$ 行应包含第 $i$ 个查询的答案。

样例

8
2 0 2 4 0 2 0 3
5
1 8 3
10 12 11
3 3 2
3 6 5
12 0 11

9
2
0
8
5

给定序列 $A=(2,0,2,4,0,2,0,3)$。

这个输入包含五个查询。

初始时 $B_0=0$。

第一个查询是 $\alpha = 1, \beta = 8, \gamma = 3$。

解密后得到 $L_i = \alpha \oplus B_0 = 1, R_i = \beta \oplus B_0 = 8, X_i = \gamma \oplus B_0 = 3$。

这个查询的答案是 $9$。将其记为 $B_1$。

下一个查询是 $\alpha = 10, \beta = 12, \gamma = 11$。

解密后得到 $L_i = \alpha \oplus B_1 = 3, R_i = \beta \oplus B_1 = 5, X_i = \gamma \oplus B_1 = 2$。

这个查询的答案是 $2$。将其记为 $B_2$。

下一个查询是 $\alpha = 3, \beta = 3, \gamma = 2$。

解密后得到 $L_i = \alpha \oplus B_2 = 1, R_i = \beta \oplus B_2 = 1, X_i = \gamma \oplus B_2 = 0$。

这个查询的答案是 $0$。将其记为 $B_3$。

下一个查询是 $\alpha = 3, \beta = 6, \gamma = 5$。

解密后得到 $L_i = \alpha \oplus B_3 = 3, R_i = \beta \oplus B_3 = 6, X_i = \gamma \oplus B_3 = 5$。

这个查询的答案是 $8$。将其记为 $B_4$。

下一个查询是 $\alpha = 12, \beta = 0, \gamma = 11$。

解密后得到 $L_i = \alpha \oplus B_4 = 4, R_i = \beta \oplus B_4 = 8, X_i = \gamma \oplus B_4 = 3$。

这个查询的答案是 $5$。将其记为 $B_5$。

数据范围

• 所有输入值均为整数
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• 对于加密输入，满足 $0 \le \alpha_i, \beta_i, \gamma_i \le 10^{18}$
• 对于解密后的查询，满足 $1 \le L_i \le R_i \le N$，且 $0 \le X_i \le 10^9$