CF1982D.Beauty of the mountains

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Nikita 喜爱山脉，终于决定前往 Berlyand 山脉旅行！山脉太美了，于是 Nikita 决定把它画在地图上。地图是一个 $n$ 行 $m$ 列的表格，每个格子里有一个非负整数，表示该处山的高度。

他还注意到山脉有两种类型：

有雪顶的山。
没有雪顶的山。

Nikita 是个非常务实的人。他希望有雪顶的山的高度之和等于没有雪顶的山的高度之和。他已经和 Berlyand 市长 Polikarp Polikarpovich 协商好，可以对地形进行改造。

Nikita 可以对任意 $k \times k$ 的子矩阵进行如下操作：他可以给该区域内所有山的高度加上一个整数常数 $c$ ，但山的类型不会改变。每次操作可以独立选择 $c$ ，且 $c$ 可以为负数。

在进行操作前，Nikita 想知道是否有可能使两类山的高度和相等，或者这是不可能的。无论付出什么代价都可以，即使山变成了峡谷，高度为负也没关系。

如果地图上只有一种类型的山，则另一种类型的山的高度和视为 $0$ 。

输入格式

每组测试数据包含若干组测试用例。第一行包含一个整数 $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_{ij}$ （ $0 \le a_{ij} \le 10^{9}$ ），表示初始的山高。

接下来的 $n$ 行，每行是一个长度为 $m$ 的二进制字符串，表示山的类型，'0' 表示有雪顶，'1' 表示无雪顶。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $250\,000$ 。

输出格式

对于每组测试用例，如果可以使两类山的高度和相等，输出 "YES"（不带引号），否则输出 "NO"（不带引号）。输出大小写不敏感（如 "yEs"、"yes"、"Yes"、"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

输出#1