Problem Statement

You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Answer the following $Q$ queries. The $i$-th query is as follows:

• Find the sum of the elements among $A_{L_i},A_{L_i+1},\dots,A_{R_i}$ that are not greater than $X_i$.

Here, you need to answer these queries online. That is, only after you answer the current query is the next query revealed.

For this reason, instead of the $i$-th query itself, you are given encrypted inputs $\alpha_i, \beta_i, \gamma_i$ for the query. Restore the original $i$-th query using the following steps and then answer it.

• Let $B_0=0$ and $B_i =$ (the answer to the $i$-th query).
• Then, the query can be decrypted as follows:
• $L_i = \alpha_i \oplus B_{i-1}$
  • $R_i = \beta_i \oplus B_{i-1}$
  • $X_i = \gamma_i \oplus B_{i-1}$

Here, $x \oplus y$ denotes the bitwise XOR of $x$ and $y$.

What is bitwise XOR? The bitwise XOR of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows: The digit in the $2^k$ place ($k \geq 0$) of $A \oplus B$ in binary is $1$ if exactly one of the corresponding digits of $A$ and $B$ in binary is $1$, and $0$ otherwise. For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

Constraints

• All input values are integers.
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• For the encrypted inputs, the following holds:
• $0 \le \alpha_i, \beta_i, \gamma_i \le 10^{18}$
• For the decrypted queries, the following holds:
• $1 \le L_i \le R_i \le N$
  • $0 \le X_i \le 10^9$

Input

The input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.