問題文

$N$ 個の命題定数 $A_1, \dots, A_N$ と $(N-1)$ 個の論理演算子 $\operatorname{op}_1, \dots, \operatorname{op}_{N-1}$ が以下のように交互に現れる列 $E$ が与えられる. $$E: (A_1, \operatorname{op}_1, A_2, \operatorname{op}_2, A_3, \dots, A_{N-2}, \operatorname{op}_{N-2}, A_{N-1}, \operatorname{op}_{N-1}, A_N)$$

ここで, $N$ 個の命題定数 $A_i$ についてはそれぞれ文字列 $X_i$ で与えられ, 以下を意味している.

• $X_i$=True のとき, $A_i$ は真である.
• $X_i$=False のとき, $A_i$ は偽である.

そして, $(N-1)$ 個の論理演算子 $\operatorname{op}_i$ についてもそれぞれ文字列 $Y_i$ で与えられ, 以下を意味している.

• $Y_i$=and のとき, $\operatorname{op}_i$ は論理積 $\land$ である.
• $Y_i$=or のとき, $\operatorname{op}_i$ は論理和 $\lor$ である.
• $Y_i$=xor のとき, $\operatorname{op}_i$ は排他的論理和 $\veebar$ である.
• $Y_i$=imp のとき, $\operatorname{op}_i$ は含意 $\to$ である.

この列 $E$ に対して, 以下の操作を $(N-1)$ 回行う. ただし, $j~(1 \leq j \leq N-1)$ 回目の操作は整数 $S_j$ を用いて表される.

• $E$ において, $S_j$ 番目の命題定数から始まる連続する長さ $3$ の部分列 $(A_{S_j}, \operatorname{op}_{S_j}, A_{S_j+1})$ を削除し, 元あった位置に $A_{S_j} \operatorname{op}_{S_j} A_{S_j+1}$ の結果を挿入する. (そして, 必要ならば, 命題定数と論理演算子それぞれについて添字を $1$ から付け替える.)

操作を $(N-1)$ 回行うことにより, $E$ はただ $1$ つの命題定数からなる列になる. では, そのただ $1$ つの命題定数とは真か? それとも偽か?

$T$ 個のテストケースについて答えよ.

注記

$P,Q$ を命題定数とする.

• $P,Q$ の論理積 $P \land Q$ は $P,Q$ の両方が真であるときは真, そうではないときは偽として定義される.
• $P,Q$ の論理和 $P \lor Q$ は $P,Q$ のうち, 少なくとも一方 (両方でも可) が真であるときは真, そうではないときは偽として定義される.
• $P,Q$ の排他的論理和 $P \veebar Q$ は $P,Q$ の真偽が異なっている場合は真, そうではないときは偽として定義される.
• $P,Q$ の含意 $P \to Q$ は $P$ が真の場合は $Q$ として, $P$ が偽である場合は真として定義される.

制約

• $1 \leq T \leq 10^5$.
• $T$ は整数である.
• 各テストケースに関する制約
• $2 \leq N$.
• $X_i$ は True または False である $\quad (1 \leq i \leq N)$.
• $Y_i$ は and, or, xor, imp のどれかである $\quad (1 \leq i \leq N-1)$.
• $1 \leq S_j \leq N-j \quad (1 \leq j \leq N-1)$.
• $N, S_j$ は整数である.
• テストファイルに関する制約
• $T$ 個のテストケースにおける $N$ の総和は $2 \times 10^5$ 以下である.

最後に改行を忘れないこと.

入力

$T$
$\text{Testcase}_1$
$\text{Testcase}_2$
$\vdots$
$\text{Testcase}_T$

$N$
$X_1$ $X_2$ $\cdots$ $X_{N-1}$ $X_N$
$Y_1$ $Y_2$ $\cdots$ $Y_{N-1}$
$S_1$ $S_2$ $\cdots$ $S_{N-1}$

出力

出力は $T$ 行からなる.

第 $t$ 行目には第 $t$ テストケースについて, 解答が真であるならば, True を, 偽であるならば, False を出力せよ.

サンプル

3
5
True False True False True
and or xor imp
2 2 1 1
3
False True False
and and
1 1
4
False True False False
imp and imp
1 2 1

True
False
True