CF1971H ±1

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, \cdots, a_n$ of her choosing, **whose elements are all $-1$ or $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.

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.

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).

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]$.