問題一覧 > 通常問題

No.2702 Nand Nor Matrix

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : hirayuu_yc / テスター : 👑 hamamu Magentor
お気に入りにしたユーザー ProblemId : 10421 / 自分の提出
問題文最終更新日: 2024-02-14 16:00:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 424 (順位表) の他の問題:

Problem Statement

In this problem, for $x,y\in \{0,1\}$, the functions $\text{nand}(x,y),\text{nor}(x,y)$ are defined as follows.

$\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}$

Haruku received an $N\times N$ matrix $X$ in which every element is $0$ or $1$. The elements of this matrix change as time passes.

More precisely, let $X_{t,i,j}$ be the element of $X$ at time $t$ in the $i$-th row from the top and the $j$-th column from the left. Then $X_{t,i,j}$ is determined by the following rules.

$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}$

Haruku cannot wait for the matrix to change, so he asked you $Q$ questions. The $i$-th question is as follows.

  • Is the value of $X_{T_i,R_i,C_i}$ $0$ or $1$?
Answer all the questions correctly.

Input

$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$
  • All input values are integers.

Output

Output $Q$ lines.

On the $i$-th line, output the answer to the $i$-th question.

Sample

Sample 1
Input
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
Output
1
0
1
0
0
1
  • $X_{0,1,1}=A_1=1$.
  • $X_{0,3,2}=0$.
  • $X_{1,3,2}=\text{nand}(X_{0,2,2},X_{0,3,1})=\text{nand}(0,B_3)=\text{nand}(0,1)=1$.
  • $X_{1,4,1}=X_{0,4,1}=B_4=0$.
  • $X_{1,2,2}=\text{nand}(X_{0,1,2},X_{0,2,1})=\text{nand}(A_2,B_2)=\text{nand}(1,1)=0$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。