問題文

長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。以下の $Q$ 個のクエリに答えてください。

• $i$ 番目のクエリ:整数 $L_i,R_i$ が与えられる。 $B=(A_{L_i},A_{L_i+1},\dots,A_{R_i})$ に対して以下の問題を解け。

  • $B$ を $3$ つの非空かつ連続とは限らない部分列 $B_1,B_2,B_3$ に分解する。$\mathrm{mex}(B_1)+\mathrm{mex}(B_2)+\mathrm{mex}(B_3)$ としてありうる値の最大値を求めよ。なお、問題文の制約から $B$ の長さは $3$ 以上になるため、 $3$ つの非空な部分列に分解する方法は必ず $1$ つ以上存在する。

但し、あなたはこのクエリにオンラインで答える必要があります。

「オンラインでクエリに答える」とは、あるクエリへの回答を行った後で次のクエリが判明することを指します。

このため、 $i$ 個目のクエリの代わりに、このクエリを暗号化した入力 $\alpha_i,\beta_i$ が与えられます。以下の手順で本来の $i$ 個目のクエリを復元して回答してください。

• $ans_0=0,ans_i=$( $i$ 番目のクエリの答え ) とする。
• このとき、クエリの復元は以下のようにして行うことができる。
• $L_i=\alpha_i\oplus ans_{i-1}$
• $R_i=\beta_i\oplus ans_{i-1}$

但し、 $x\oplus y$ は $x$ と $y$ のビット単位XOR を表します。

制約

• $1\leq N\leq 10^5$
• $0\leq A_i\leq 10^5$
• $1\leq Q\leq 10^5$
• 暗号化されたクエリに対して、以下が成立する。
• $0\leq\alpha_i,\beta_i\leq 10^{18}$
• 復元した後のクエリに対して、以下が成立する。
• $1\leq L_i\leq R_i\leq N$
• $R_i-L_i\geq 2$

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$Q$
$\alpha_1$ $\beta_1$
$\alpha_2$ $\beta_2$
$\vdots$
$\alpha_N$ $\beta_N$

出力

最後に改行してください。

サンプル

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