Никита любит горы и наконец-то решил посетить Берляндский горный хребет! Хребет был настолько красив, что Никита решил запечатлеть его на карте. Карта представляет собой таблицу из $$$n$$$ строк и $$$m$$$ столбцов, в каждой клетке записано целое неотрицательное число — высота этой горы.
Также он заметил, что горы бывают двух типов:
- Со снежными шапками.
- Без снежных шапок.
Никита — человек очень прагматичный. Он хочет, чтобы сумма всех высот гор со снежными шапками была равна сумме высот гор без них. Он договорился с мэром Берляндии, самим Поликарпом Поликарповичем, чтобы тот разрешил ему трансформировать ландшафт.
Никита может проводить трансформации подматриц размером $$$k \times k$$$ следующим образом: к высотам гор, попавших в этот участок, прибавляется целочисленная константа $$$c$$$, но при этом тип гор не меняется. При этом константу $$$c$$$ Никита может выбирать для каждой трансформации независимо от предыдущих. Обратите внимание, что $$$c$$$ может быть отрицательной.
Прежде чем производить трансформации, Никита просит у вас узнать, возможно ли добиться равенства сумм, или это сделать невозможно. Неважно, какой ценой, даже если горы превратятся в каньоны и будут иметь отрицательную высоту.
Если на карте представлен только один тип гор, то сумма высот другого типа гор принимается равной нулю.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n, m, k$$$ ($$$1 \le n, m \le 500, 1 \le k \le min(n, m)$$$).
Следующие $$$n$$$ строк каждого набора входных данных содержат по $$$m$$$ целых чисел $$$a_{i j}$$$ ($$$0 \le a_{i j} \le 10^{9}$$$) — изначальные высоты гор.
Следующие $$$n$$$ бинарных строк длины $$$m$$$ каждого набора входных данных определяют тип гор, '$$$0$$$' — со снежными шапками, '$$$1$$$' — без них.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$250\,000$$$.
Для каждого набора входных данных выведите «YES» без кавычек, если можно уравнять суммы высот гор, иначе выведите «NO» без кавычек. Вы можете вывести каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
83 3 27 11 34 2 30 1 151000100004 4 3123 413 24 233123 42 0 21622 1 1 53427 763 22 601011111101001013 3 22 1 11 1 21 5 40101010103 3 22 1 11 1 21 5 30101010103 4 346 49 50 119 30 23 1230 25 1 461000010000105 4 439 30 0 1722 42 30 1310 44 46 3512 19 9 3921 0 45 40100011110011011111002 2 23 46 700002 2 20 02 00100
YES NO YES NO YES NO 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.
