C. Нулевой путь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана таблица с $$$n$$$ строк и $$$m$$$ столбцов. Обозначим ячейку в $$$i$$$-й ($$$1\le i\le n$$$) строке и $$$j$$$-м ($$$1\le j\le m$$$) столбце через $$$(i, j)$$$, а число в ней через $$$a_{ij}$$$. Все числа равны $$$1$$$ или $$$-1$$$.

Вы начинаете с ячейки $$$(1, 1)$$$ и можете перемещаться на одну ячейку вниз или вправо за один раз. В конце концов, вы хотите оказаться в ячейке $$$(n, m)$$$.

Можно ли двигаться таким образом, чтобы сумма значений, записанных во всех посещенных ячейках (включая $$$a_{11}$$$ и $$$a_{nm}$$$), была равна $$$0$$$?

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 1000$$$)  — размер таблицы.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел. $$$j$$$-е целое число в $$$i$$$-й строке это $$$a_{ij}$$$ ($$$a_{ij} = 1$$$ или $$$-1$$$)  — элемент в ячейке $$$(i, j)$$$.

Гарантируется, что сумма $$$n\cdot m$$$ по всем наборам входных данных не превышает $$$10^6$$$.

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

Для каждого набора входных данных выведите «YES», если существует путь из левого верхнего угла в правый нижний, который дает в сумме $$$0$$$, и «NO» в противном случае. Вы можете выводить каждую букву в любом регистре.

Пример
Входные данные
5
1 1
1
1 2
1 -1
1 4
1 -1 1 -1
3 4
1 -1 -1 -1
-1 1 1 -1
1 1 1 -1
3 4
1 -1 1 1
-1 1 -1 1
1 -1 1 1
Выходные данные
NO
YES
YES
YES
NO
Примечание

Один из возможных путей для четвертого набора входных данных приведен на рисунке в утверждении.