長さ $N$ の数式 $S$ が与えられる。 数式は、以下の BNF で示される形式になっている。
<expr> ::= <number> | <expr> <op> <expr>
<op> ::= ‘^’ | ‘&’ | ‘|’
<number> は、 $0$ 以上 $2^{31}-1$ 以下の整数を表す。
演算子、’^’ ‘&’ ‘|’ は、それぞれ排他的論理和、論理積、論理和を表す。 演算子の優先順位は以下の通りである。
高 ’^’ > ‘&’ > ‘|’ 低
区間 $[i, j]$ が $Q$ 個与えられる。 $S_i, \dots , S_j$ の計算結果を出力せよ。
なお、数式 $S_i, \dots , S_j$ が上記のBNFで示される形式であることは保証される。また、数式にゼロ詰めされた値が含まれることはない。
入力は以下の形式で与えられる。
$N$
$S$
$Q$
$i_1\ j_1$
$\vdots$
$i_Q\ j_Q$
$S_i, \dots , S_j$ の計算結果を出力せよ。 また、末尾に改行も出力せよ。
7 9^2&1|2 4 0 6 0 2 2 6 4 4
3 11 2 1
13 3423&423^1234 3 2 12 5 9 9 12
21 422 1234
7 1234567 3 0 0 0 1 4 6
1 12 567