D. Красота гор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Никита любит горы и наконец-то решил посетить Берляндский горный хребет! Хребет был настолько красив, что Никита решил запечатлеть его на карте. Карта представляет собой таблицу из $$$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» будут распознаны как положительный ответ).

Пример
Входные данные
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
Примечание

Горный массив из первого набора данных выглядит так:

Изначально сумма высот гор со снежными шапками равна $$$11 + 3 + 4 + 3 + 0 + 1 + 15 = 37$$$, а без них $$$7 + 2 = 9$$$.

Чтобы уравнять эти суммы, мы можем выполнить две трансформации:

Первая трансформация:

Обратите внимание, что константа $$$c$$$ может быть отрицательной.

После первой трансформации горный массив выглядит так:

Вторая трансформация:

В результате горный массив выглядит так:

Сумма высот гор со снежными шапками равна $$$17 + 9 + 9 - 16 - 20 - 19 + 15 = -5$$$, а без них $$$7 - 12 = -5$$$, таким образом ответ YES.