H. ±1
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Боба есть таблица с $$$3$$$ строками и $$$n$$$ столбцами, в каждом из которых находится либо $$$a_i$$$, либо $$$-a_i$$$ для некоторого целого числа $$$1 \leq i \leq n$$$. Например, одна из возможных сеток для $$$n=4$$$ показана ниже:

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

Алиса и Боб играют в игру следующим образом:

  • Боб показывает Алисе свою сетку.
  • Алиса дает Бобу массив $$$a_1, a_2, \dots, a_n$$$, который она выбирает, элементы которого либо $$$\mathbf{-1}$$$, либо $$$\mathbf{1}$$$.
  • Боб подставляет эти значения в свою сетку, чтобы получить сетку из $$$-1$$$ и $$$1$$$.
  • Боб сортирует элементы каждого столбца в неубывающем порядке.
  • Алиса выигрывает, если все элементы в средней строке равны $$$1$$$; в противном случае выигрывает Боб.

Например, предположим, что Алиса дает Бобу массив $$$[1, -1, -1, 1]$$$ для приведенной выше сетки. Тогда произойдет следующее (цвета добавлены для ясности):

$$$$$$\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{сортировка каждого столбца}} \begin{bmatrix} -1 & -1 & -1 & 1 \\ \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}\,. $$$$$$ Поскольку средняя строка состоит только из $$$1$$$, Алиса выигрывает.

Учитывая сетку Боба, определите, может ли Алиса выбрать массив $$$a$$$ и выиграть игру.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 500$$$) — количество столбцов сетки Боба.

Следующие три строки содержат по $$$n$$$ целых чисел, $$$i$$$-я из которых содержит $$$g_{i,1}, g_{i,2}, \dots, g_{i,n}$$$ ($$$-n \leq g_{i,j} \leq n$$$, $$$g_{i,j} \neq 0$$$), представляющих сетку Боба.

Если ячейка $$$x > 0$$$ присутствует во входных данных, то эта ячейка в сетке Боба должна содержать $$$a_x$$$; если $$$x < 0$$$ присутствует во входных данных, то эта ячейка в сетке Боба должна содержать $$$-a_{-x}$$$. Для лучшего понимания смотрите пример ввода и примечание.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если Алиса может выиграть, и «NO» (без кавычек) в противном случае.

Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», и «Yes» будут распознаны как положительный ответ).

Пример
Входные данные
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
Выходные данные
YES
NO
YES
NO
Примечание

Первый пример описан в условии.

Во втором примере сетка Боба выглядит следующим образом:

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

Чтобы в последнем столбце была $$$1$$$ в средней строке после сортировки, Алиса должна выбрать $$$a_2 = -1$$$. Однако тогда невозможно выбрать $$$a_1$$$ так, чтобы первый столбец имел $$$1$$$ в средней строке после сортировки. Таким образом, Алиса не может выиграть.

В третьем примере Алиса может выбрать $$$a = [1,1,1,1,1]$$$.