311343: CF1971H. ±1

H. ±1time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Bob has a grid with $3$ rows and $n$ columns, each of which contains either $a_i$ or $-a_i$ for some integer $1 \leq i \leq n$. For example, one possible grid for $n=4$ is shown below:

$$\begin{bmatrix} a_1 & -a_2 & -a_3 & -a_2 \\ -a_4 & a_4 & -a_1 & -a_3 \\ a_1 & a_2 & -a_2 & a_4 \end{bmatrix}$$

Alice and Bob play a game as follows:

• Bob shows Alice his grid.
• Alice gives Bob an array $a_1, a_2, \dots, a_n$ of her choosing, whose elements are all $\mathbf{-1}$ or $\mathbf{1}$.
• Bob substitutes these values into his grid to make a grid of $-1$s and $1$s.
• Bob sorts the elements of each column in non-decreasing order.
• Alice wins if all the elements in the middle row are $1$; otherwise, Bob wins.

For example, suppose Alice gives Bob the array $[1, -1, -1, 1]$ for the grid above. Then the following will happen (colors are added for clarity):

$$\begin{bmatrix} \color{red}{a_1} & \color{green}{-a_2} & \color{blue}{-a_3} & \color{green}{-a_2} \\ -a_4 & a_4 & \color{red}{-a_1} & \color{blue}{-a_3} \\ \color{red}{a_1} & \color{green}{a_2} & \color{green}{-a_2} & a_4 \end{bmatrix} \xrightarrow{[\color{red}{1},\color{green}{-1},\color{blue}{-1},1]} \begin{bmatrix} \color{red}{1} & \color{green}{1} & \color{blue}{1} & \color{green}{1} \\ -1 & 1 & \color{red}{-1} & \color{blue}{1} \\ \color{red}{1} & \color{green}{-1} & \color{green}{1} & 1 \end{bmatrix} \xrightarrow{\text{sort each column}} \begin{bmatrix} -1 & -1 & -1 & 1 \\ \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}\,. $$ Since the middle row is all $1$, Alice wins.

Given Bob's grid, determine whether or not Alice can choose the array $a$ to win the game.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 500$) — the number of columns of Bob's grid.

The next three lines each contain $n$ integers, the $i$-th of which contains $g_{i,1}, g_{i,2}, \dots, g_{i,n}$ ($-n \leq g_{i,j} \leq n$, $g_{i,j} \neq 0$), representing Bob's grid.

If cell $x > 0$ is in the input, that cell in Bob's grid should contain $a_x$; if $x < 0$ is in the input, that cell in Bob's grid should contain $-a_{-x}$. See the sample input and notes for a better understanding.

Output

For each test case, output "YES" (without quotes) if Alice can win, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", and "Yes" will be recognized as a positive response).

ExampleInput

4
4
1 -2 -3 -2
-4 4 -1 -3
1 2 -2 4
2
1 2
-1 -2
2 -2
5
1 2 3 4 5
-2 3 -4 -5 -1
3 -5 1 2 2
6
1 3 -6 2 5 2
1 3 -2 -3 -6 -5
-2 -1 -3 2 3 1

Output

YES
NO
YES
NO

Note

The first test case is described in the statement.

In the second test case, Bob's grid is as follows:

$$\begin{bmatrix} a_1 & a_2 \\ -a_1 & -a_2 \\ a_2 & -a_2 \end{bmatrix}$$

For the last column to have $1$ in the middle row when sorted, Alice must pick $a_2 = -1$. However, it is then impossible to choose $a_1$ such that the first column has $1$ in the middle when sorted. Thus, Alice cannot win.

In the third test case, Alice can pick $a = [1,1,1,1,1]$.

题目大意：
Bob有一个3行n列的网格，每个格子包含a_i或-a_i（1≤i≤n）。Alice和Bob进行以下游戏：
1. Bob向Alice展示他的网格。
2. Alice给Bob一个由-1或1组成的数组a_1, a_2, ..., a_n。
3. Bob将这些值替换到他的网格中，使其变为由-1和1组成的网格。
4. Bob将每列的元素按非降序排序。
5. 如果中间行的所有元素都是1，则Alice赢；否则，Bob赢。

输入数据格式：
第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
每个测试用例的第一行包含一个整数n（2≤n≤500）——Bob网格的列数。
接下来三行，每行包含n个整数，表示Bob的网格。

输出数据格式：
对于每个测试用例，如果Alice能赢，输出"YES"；否则输出"NO"。题目大意： Bob有一个3行n列的网格，每个格子包含a_i或-a_i（1≤i≤n）。Alice和Bob进行以下游戏： 1. Bob向Alice展示他的网格。 2. Alice给Bob一个由-1或1组成的数组a_1, a_2, ..., a_n。 3. Bob将这些值替换到他的网格中，使其变为由-1和1组成的网格。 4. Bob将每列的元素按非降序排序。 5. 如果中间行的所有元素都是1，则Alice赢；否则，Bob赢。 输入数据格式： 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 每个测试用例的第一行包含一个整数n（2≤n≤500）——Bob网格的列数。 接下来三行，每行包含n个整数，表示Bob的网格。 输出数据格式： 对于每个测试用例，如果Alice能赢，输出"YES"；否则输出"NO"。