Cycle XOR Walk

問題文

$N$ 頂点 $N$ 辺の有向グラフがある。 このグラフの辺 $i$ は 頂点 $i$ から頂点 $i+1$ へ$(1 \leq i \leq N)$ 繋いでいる。 (辺 $N$ は頂点 $N$ から 頂点$1$へ繋いでいるものとする。) また、各頂点には 重み があり、頂点 $i$ の重みは $W_i$ である。

次の $Q$ 個のクエリに答えよ。$(1 \leq j \leq Q)$

• 頂点 $s_j$ から $t_j$ への walk のうち、 walk に含まれる頂点の重みのビット単位 $XOR$ の最大値を求めよ。

- 頂点 $s_j$ から $t_j$ への walkとは

直感的には、「頂点 $s_j$ から $t_j$ への経路であって、 同じ頂点や同じ辺を複数回通っても良いもの」である。 walk に含まれる頂点とは、頂点の列 $(v_1,...,v_k)$ であって、以下の条件を全て満たすものである。

• $v_1 = s_j$ である。
• 全ての $(1 \leq i \leq k-1)$ について、頂点 $v_i$ と頂点 $v_{i+1}$ を繋ぐ辺が存在する。
• $v_k = t_j$ である。

- ビット単位 $XOR$ 演算とは

非負整数 $A,B$ のビット単位 $XOR$ である $A$ $XOR$ $B$ は、以下のように定義される。

• $A$ $XOR$ $B$ を2進表記した際の $2^k(k \leq 0)$ の位の数は、 $A,B$ を2進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、 そうでなければ $0$である。

例えば、$3 XOR 5 = 6$ である。(二進表記:$011 XOR 101 = 110$)

一般に $k$ 個の非負整数 $p_1,p_2,p_3,...,p_k$ のビット単位 $XOR$ は $(...((p_1 XOR p_2) XOR p_3) XOR ... XOR p_k)$ と定義され、これは $p_1,p_2,p_3,...,p_k$の順番によらないことが証明できる。

制約

• $2 \leq N \leq 10^{5}$
• $0 \leq W_i < 2^{30}(1 \leq i \leq N)$
• $1 \leq Q \leq 10^{5}$
• $1 \leq s_j,t_j \leq N(1 \leq j \leq Q)$
• $s_j \neq t_j$

入力

入力はすべて整数である。

N
W_1 W_2 ... W_N
Q
s_1 t_1
s_2 t_2
...
s_Q t_Q

出力

各クエリ $1 \leq j \leq Q$ について、頂点 $s_j$ から $t_j$ への walk のうち、 walk に含まれる頂点の重みのビット単位 $XOR$ の最大値を1行づつ出力せよ。

サンプル

4
1 2 4 0
1
1 3

7

例えば $1 \rightarrow 2 \rightarrow 3$ と移動すると、 この walk に含まれる頂点の重みのビット単位 $XOR$ は$1 XOR 2 XOR 4 = 7$ となります。 これよりも頂点の重みのビット単位 $XOR$ の値を大きくすることはできないので、 $7$ を出力します。このような walk は他にも、$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3$ などが考えられます。

5
16 17 3 4 8
2
1 3
2 3

12
28

6
55 17 30 42 18 76
3
1 3
2 6
5 4

116
123
76