У Маши есть \(n\) типов плиток размера \(2 \times 2\). В каждой из четырех клеток плитки записано по одному целому числу. У Маши есть неограниченное количество плиток каждого из типов.
Маша решила выложить из своих плиток квадрат размера \(m \times m\), причем этот квадрат должен представлять из себя симметричную относительно главной диагонали матрицу, а каждая клетка квадрата должна быть покрыта ровно одной клеткой плитки, причем боковые стороны плиток после укладки должны быть параллельны боковым сторонам квадрата. Уложенные плитки не должны пересекаться между собой. Также плитки должны целиком лежать внутри квадрата. Рассмотрите рисунок из примечания для лучшего понимания условия.
Симметричная относительно главной диагонали матрица — это квадрат \(s\), у которого для всех пар \((i, j)\) верно, что \(s[i][j] = s[j][i]\). То есть для всех клеток верно, что элемент, записанный на пересечении \(i\)-й строки и \(j\)-го столбца равен элементу, который записан на пересечении \(j\)-й строки и \(i\)-го столбца.
Перед вами стоит задача определить, сможет ли Маша выложить из своих плиток квадрат размера \(m \times m\), который будет представлять из себя симметричную матрицу. Для укладки Маша может использовать неограниченное количество плиток каждого из имеющихся у нее типов. Обратите внимание, что плитки нельзя поворачивать, их можно укладывать только в той ориентации, в которой они заданы во входных данных.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Выведите ответ на каждый набор тестовых данных: если Маша может выложить из своих плиток квадрат размера \(m \times m\), который будет являться симметричной матрицей, выведите «YES» (без кавычек). В противном случае выведите «NO» (без кавычек).
Примечание
В первом наборе тестовых данных есть три типа плиток, они изображены на рисунке.
Из таких типов плиток можно составить, например, такой квадрат размера \(4 \times 4\), который является симметричной матрицей:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 4
1 2
5 6
5 7
7 4
8 9
9 8
2 5
1 1
1 1
2 2
2 2
1 100
10 10
10 10
1 2
4 5
8 4
2 2
1 1
1 1
1 2
3 4
1 2
1 1
1 1
|
YES
NO
YES
NO
YES
YES
|