G: 式の切り取り

問題

長さ $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で示される形式であることは保証される。また、数式にゼロ詰めされた値が含まれることはない。

制約

• $1 \leq N, Q \leq 10^5$
• $N = |S| \ \ \ \ \ |S|$ は文字列の長さを表す。
• $0 \leq i \leq j < N$

入力形式

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

$N$
$S$
$Q$
$i_1\ j_1$
$\vdots$
$i_Q\ j_Q$

出力

$S_i, \dots , S_j$ の計算結果を出力せよ。 また、末尾に改行も出力せよ。

サンプル

サンプル入力 1

7
9^2&1|2
4
0 6
0 2
2 6
4 4

サンプル出力 1

3
11
2
1

サンプル入力 2

13
3423&423^1234
3
2 12
5 9
9 12

サンプル出力 2

21
422
1234

サンプル入力 3

7
1234567
3
0 0
0 1
4 6

サンプル出力 3

1
12
567

Note

Commentary

 

---