Вам задано поле Тетриса, состоящее из \(n\) столбцов. Начальная высота \(i\)-го столбца поля равна \(a_i\) блоков. Сверху на столбцы вы можете ставить только фигуры размера \(2 \times 1\) (то есть высоты \(2\) блока и ширины \(1\) блок). Заметьте, что вы не можете поворачивать эти фигуры.
Ваша задача — определить, возможно ли очистить заданное поле, используя только описанные фигуры.
Более формально, задачу можно описать следующим образом:
Пока хотя бы одно из \(a_i\) больше \(0\), происходит следующий процесс:
- Вы ставите одну фигуру \(2 \times 1\) (выбираете какое-то \(i\) от \(1\) до \(n\) и заменяете \(a_i\) на \(a_i + 2\));
- затем, пока все \(a_i\) больше нуля, каждое \(a_i\) заменяется на \(a_i - 1\).
Ваша задача — определить, возможно ли очистить заданное поле (т.е. завершить описанный процесс), выбирая места для новых фигур правильным образом.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ — «YES» (без кавычек), если вы можете очистить поле тетриса полностью, и «NO» в противном случае.
Примечание
Первый набор тестовых данных из примера показан ниже:
Серые линии означают границы поля Тетриса. Заметьте, что поле не имеет верхней границы.
Одним из корректных ответов является сначала поставить фигуру в первый столбец. Затем, после второго шага процесса, поле станет равно \([2, 0, 2]\). Затем надо поставить фигуру во второй столбец и после второго шага процесса поле станет равно \([0, 0, 0]\).
И второй набор тестовых данных из примера показан ниже:
Можно показать, что вы не можете сделать ничего, чтобы закончить процесс.
В третьем наборе тестовых данных из примера можно сначала поставить фигуру во второй столбец и после второго шага процесса поле станет равно \([0, 2]\). Затем можно поставить фигуру в первый столбец и после второго шага процесса поле станет равно \([0, 0]\).
В четвертом наборе тестовых данных из примера можно поставить фигуру в первый столбец, тогда после первого шага процесса поле станет равно \([102]\), и затем после второго шага процесса поле станет равно \([0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 1 3
4
1 1 2 1
2
11 11
1
100
|
YES
NO
YES
YES
|