問題文

本問題では、$x,y\in \{0,1\}$ として、$\text{nand}(x,y),\text{nor}(x,y)$ を以下のような関数とします。

$\text{nand}(x,y)=\begin{cases}0\ (x=1 \land y=1)\\1\ (\text{otherwise.})\end{cases}$

$\text{nor}(x,y)=\begin{cases}1\ (x=0 \land y=0)\\0\ (\text{otherwise.})\end{cases}$

はるく君は、すべての要素が $0$ または $1$ からなる $N\times N$ 行列 $X$ をもらいました。この行列は、時間がたつごとに要素が変化します。

正確には、$X$ の時刻 $t$ での上から $i$ 行目、左から $j$ 列目の要素を $X_{t,i,j}$ とするとき、$X_{t,i,j}$ は以下の規則で決まります。

$X_{t,i,j}=\begin{cases}A_j\ (t=0\land i=1)\\B_i\ (t=0\land i\ne 1 \land j=1)\\0\ (t=0\land i\ne 1 \land j\ne 1)\\X_{t-1,i,j}\ (t>0\land (i=1\lor j=1))\\\text{nand}(X_{t-1,i-1,j},X_{t-1,i,j-1})\ (t>0 \land i\ne 1\land j\ne 1\land X_{t-1,i,j}=0)\\\text{nor}(X_{t-1,i-1,j},X_{t-1,i,j-1})\ (t>0 \land i\ne 1\land j\ne 1\land X_{t-1,i,j}=1)\\\end{cases}$

はるく君は行列が変化するのが待ちきれないので、あなたに $Q$ 個の質問をしました。$i$ 番目の質問内容は以下の通りです。

• $X_{T_i,R_i,C_i}$ の値は $0$ と $1$ のどちらか？

入力

$N$
$A_1\ A_2\ \dots\ A_N$
$B_2$
$B_3$
$\vdots$
$B_N$
$Q$
$T_1\ R_1\ C_1$
$T_2\ R_2\ C_2$
$\vdots$
$T_Q\ R_Q\ C_Q$

• $1\leq N,Q\leq 2\times 10^5$
• $A_i,B_i\in \{0,1\}$
• $0\leq T_i\leq 10^{18}$
• $1\leq R_i,C_i\leq N$
• 入力はすべて整数

出力

$Q$ 行出力してください。

$i$ 行目には、$i$ 番目の質問に対する答えを出力してください。

サンプル

4
1 1 0 1
1
1
0
6
0 1 1
0 3 2
1 3 2
1 4 1
1 2 2
998244353 4 4

1
0
1
0
0
1