У Боба есть таблица с \(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\) и выиграть игру.
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если Алиса может выиграть, и «NO» (без кавычек) в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», и «Yes» будут распознаны как положительный ответ).
Примечание
Первый пример описан в условии.
Во втором примере сетка Боба выглядит следующим образом:
\(\)\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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|