Nikita 热爱山脉,终于决定去参观 Berlyand 山脉!这个山脉是如此美丽,尼基塔决定在地图上捕捉它。该地图是一个由 $$$n$$$ 行和 $$$m$$$ 列组成的表格,每个单元格包含一个表示山的高度的非负整数。
他还注意到山脉有两种类型:
- 带有雪帽。
- 没有雪帽。
Nikita 是一个非常务实的人。他希望有雪冠的山脉的高度总和等于没有雪冠的山脉的高度总和。他已与别尔扬德市市长波利卡尔普·波利卡尔波维奇 (Polikarp Polikarpovich) 达成协议,允许他改造当地的景观。
Nikita 可以对大小为 $$$k \times k$$$ 的子矩阵执行如下变换:他可以将整数常量 $$$c$$$ 添加到该区域内的山脉高度,但山脉的类型保持不变。 Nikita 可以为每个变换独立选择常数 $$$c$$$。请注意,$$$c$$$ 可以为负数。
在进行转换之前,Nikita 要求您弄清楚是否有可能实现总和相等,或者是否不可能。即使山脉变成峡谷并且高度为负,付出什么代价也没关系。
如果地图上只显示一种类型的山,则另一种类型山的高度总和被视为零。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$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”将被识别为肯定答案)。
示例
输入 #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
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。