Никита любит горы и наконец-то решил посетить Берляндский горный хребет! Хребет был настолько красив, что Никита решил запечатлеть его на карте. Карта представляет собой таблицу из \(n\) строк и \(m\) столбцов, в каждой клетке записано целое неотрицательное число — высота этой горы.
Также он заметил, что горы бывают двух типов:
- Со снежными шапками.
- Без снежных шапок.
Никита — человек очень прагматичный. Он хочет, чтобы сумма всех высот гор со снежными шапками была равна сумме высот гор без них. Он договорился с мэром Берляндии, самим Поликарпом Поликарповичем, чтобы тот разрешил ему трансформировать ландшафт.
Никита может проводить трансформации подматриц размером \(k \times k\) следующим образом: к высотам гор, попавших в этот участок, прибавляется целочисленная константа \(c\), но при этом тип гор не меняется. При этом константу \(c\) Никита может выбирать для каждой трансформации независимо от предыдущих. Обратите внимание, что \(c\) может быть отрицательной.
Прежде чем производить трансформации, Никита просит у вас узнать, возможно ли добиться равенства сумм, или это сделать невозможно. Неважно, какой ценой, даже если горы превратятся в каньоны и будут иметь отрицательную высоту.
Если на карте представлен только один тип гор, то сумма высот другого типа гор принимается равной нулю.
Выходные данные
Для каждого набора входных данных выведите «YES» без кавычек, если можно уравнять суммы высот гор, иначе выведите «NO» без кавычек. Вы можете вывести каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
Примечание
Горный массив из первого набора данных выглядит так:
Изначально сумма высот гор со снежными шапками равна \(11 + 3 + 4 + 3 + 0 + 1 + 15 = 37\), а без них \(7 + 2 = 9\).
Чтобы уравнять эти суммы, мы можем выполнить две трансформации:
Первая трансформация:
Обратите внимание, что константа \(c\) может быть отрицательной.
После первой трансформации горный массив выглядит так:
Вторая трансформация:
В результате горный массив выглядит так:
Сумма высот гор со снежными шапками равна \(17 + 9 + 9 - 16 - 20 - 19 + 15 = -5\), а без них \(7 - 12 = -5\), таким образом ответ YES.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3 3 2
7 11 3
4 2 3
0 1 15
100
010
000
4 4 3
123 413 24 233
123 42 0 216
22 1 1 53
427 763 22 6
0101
1111
1010
0101
3 3 2
2 1 1
1 1 2
1 5 4
010
101
010
3 3 2
2 1 1
1 1 2
1 5 3
010
101
010
3 4 3
46 49 50 1
19 30 23 12
30 25 1 46
1000
0100
0010
5 4 4
39 30 0 17
22 42 30 13
10 44 46 35
12 19 9 39
21 0 45 40
1000
1111
0011
0111
1100
2 2 2
3 4
6 7
00
00
2 2 2
0 0
2 0
01
00
|
YES
NO
YES
NO
YES
NO
YES
YES
|