Problem Statement

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

• $i$-th query: You are given integers $L_i,R_i$. Solve the following problem for $B=(A_{L_i},A_{L_i+1},\dots,A_{R_i})$.

  • Decompose $B$ into $3$ non-empty, not necessarily contiguous subsequences $B_1,B_2,B_3$. Find the maximum possible value of $\mathrm{mex}(B_1)+\mathrm{mex}(B_2)+\mathrm{mex}(B_3)$. Note that, by the constraints of the problem, the length of $B$ is at least $3$, so there is always at least $1$ way to decompose it into $3$ non-empty subsequences.

However, you must answer these queries online.

"Answering queries online" means that the next query becomes known only after you have answered the current query.

For this reason, instead of the $i$-th query itself, you are given the encrypted input $\alpha_i,\beta_i$ of this query. Restore the original $i$-th query by the following procedure and answer it.

• Let $ans_0=0,ans_i=$ (the answer to the $i$-th query).
• Then, the query can be restored as follows.
• $L_i=\alpha_i\oplus ans_{i-1}$
• $R_i=\beta_i\oplus ans_{i-1}$

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

Constraints

• $1\leq N\leq 10^5$
• $0\leq A_i\leq 10^5$
• $1\leq Q\leq 10^5$
• The following holds for the encrypted queries.
• $0\leq\alpha_i,\beta_i\leq 10^{18}$
• The following holds for the restored queries.
• $1\leq L_i\leq R_i\leq N$
• $R_i-L_i\geq 2$

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$
$\alpha_2$ $\beta_2$
$\vdots$
$\alpha_N$ $\beta_N$

Output

Print a newline at the end.

Sample

10
5 4 1 0 3 2 1 7 3 0
5
1 10
11 2
5 12
7 1
4 15

8
6
6
5
8

5
0 1 1 4 0
3
1 4
3 6
3 6

2
2
2

20
14 2 3 2 2 12 15 1 9 15 3 4 0 14 1 0 5 2 0 7
10
2 18
3 30
10 28
10 7
6 19
11 25
15 26
8 25
11 29
7 31

10
8
11
0
9
9
9
9
11
5