C1787 [Contest #12]Binary Matrix Transform

内存限制:256 MB 时间限制:1000 ms

题目描述

给出两个$n \times m$的$01$矩阵$A$和$B$,每行上往下依次编号为$1, 2, \dots, n$,每列从左往右依次标号为$1,2,\dots,m$。

你每次可以选$A$里面两个位置$(r_1,c_1)$和$(r_2,c_2)$ ($1 \le r_1, r_2 \le n, 1 \le c_1, c_2 \le m$),满足$r_1=r_2,|c_1-c_2|=c$或者$c_1=c_2,|r_1-r_2|=r$,然后你可以这两个位置上的数字取反($1$变成$0$,$0$变成$1$)。

问能否从$A$变成$B$。

输入格式

输入有多组数据。第一行有一个整数$T$,表示测试数据组数。然后对于每组数据:

第一行包含$4$个正整数$n$,$m$,$r$和$c$ ($1 \le nm \le 10^6, 1 \le r, c \le 2$)。

接下来$n$行,每行包含一个长度为$m$的$01$串,代表矩阵$A$。

再接下来$n$行,每行包含一个长度为$m$的$01$串,代表矩阵$B$。

保证所有数据中$nm$的和不超过$10^6$。

输出

对于每组数据,输出Yes或者No,表示是否能够从$A$变成$B$。

样例

样例输入 1

3 2 3 1 1 000 000 011 110 2 3 1 1 000 000 111 111 2 3 2 1 000 000 111 111

样例输出 1

Yes Yes No

提示