問題文

二項演算子 $\clubsuit$ は以下を満たします。

• $0\ \clubsuit\ 0 = S_{00}$
• $0\ \clubsuit\ 1 = S_{01}$
• $1\ \clubsuit\ 0 = S_{10}$
• $1\ \clubsuit\ 1 = S_{11}$

長さ $N$ の $0$ または $1$ で構成された数列 $A=(A_1,A_2,\dots ,A_N)$ が与えられます。 この数列に対して $Q$ 個のクエリを順に処理してください。

$i$ 番目のクエリでは、$T_i, X_i, Y_i$ が与えられます。$T_i$ に応じて以下の処理を行ってください。

• $T_i=1$ のとき：$A_{X_i}$ を $Y_i$ に置き換える
• $T_i=2$ のとき：$(\dots (A_{X_i}\ \clubsuit\ A_{X_i+1})\ \clubsuit\ A_{X_i+2})\ \clubsuit\ \dots )\ \clubsuit\ A_{Y_i})$ を出力する。

制約

• 入力はすべて整数
• $0\le S_{00},S_{01},S_{10},S_{11} \le 1$
• $2\le N,Q\le 3\times 10^5$
• $0\le A_i\le 1$
• $1\le T_i\le 2$
• $1\le X_i\le N$
• $0\le Y_i\le 1\ (T_i=1)$
• $1\le X_i\le Y_i\le N\ (T_i=2)$

入力

出力

$T_i=2$ のクエリについて順に出力し、出力毎に改行してください。

サンプル

0 1 1 1
3 3
1 0 1
2 2 3
1 1 0
2 1 2

1
0

このケースでは、$\clubsuit$ はビットごとの論理和を表します。はじめ $A=(1,0,1)$ です。

$1$ 番目のクエリでは $A_2\ \clubsuit\ A_3 = 1$ を出力します。

$2$ 番目のクエリでは $A_1$ を $0$ に置き換えます。この時点で $A=(0,0,1)$ です。

$3$ 番目のクエリでは $A_1\ \clubsuit\ A_2 = 0$ を出力します。

1 0 1 0
3 3
0 1 0
2 1 3
1 2 0
2 1 3

1
1

このケースでは、$\clubsuit$ は交換則や結合則を満たしていないことに注意しましょう。はじめ $A=(0,1,0)$ です。

$1$ 番目のクエリでは $(A_1\ \clubsuit\ A_2)\ \clubsuit\ A_3 =(0\ \clubsuit\ 1)\ \clubsuit\ 0 = 0\ \clubsuit\ 0 = 1$ を出力します。

$2$ 番目のクエリでは $A_2$ を $0$ に置き換えます。この時点で $A=(0,0,0)$ です。

$3$ 番目のクエリでは $(A_1\ \clubsuit\ A_2)\ \clubsuit\ A_3 = (0\ \clubsuit\ 0)\ \clubsuit\ 0 = 1\ \clubsuit\ 0 = 1$ を出力します。