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