#P17858. [Ontak2019]TES

[Ontak2019]TES

— 反应堆测试

有一个 n×nn\times n 的瓷砖方阵。每块瓷砖四条边上恰有两个 00 和两个 11,瓷砖分为两类:

  • A:相对的两边标记相同。按“上、右、下、左”顺序,一个初始朝向是 (0,1,0,1)(0,1,0,1)。
  • B:两个 11 相邻。一个初始朝向是 (1,1,0,0)(1,1,0,0)。

每块瓷砖可独立旋转 0∘,90∘,180∘,270∘0^\circ,90^\circ,180^\circ,270^\circ,不能移动位置。相邻瓷砖接触的两条边必须标记相同。

给定 qq 种外边界要求。对每种要求,判断能否通过旋转各块瓷砖,使所有内部接触边匹配,并使外边界符合要求。各次询问相互独立。

输入格式

第一行两个整数 n,qn,q。接下来 nn 行,每行一个长度为 nn 的字符串,由 A、B 组成,描述各块瓷砖类型。

接下来每次询问占四行,每行一个长度为 nn 的二进制串,依次描述上、下、左、右边界。上、下边界从左到右读取;左、右边界从上到下读取。

输出格式

每次询问输出一行 YES 或 NO。

数据范围

1≤n,q≤20001\le n,q\le2000。

子任务 附加限制 分值
1 n≤4,q≤30n\le4,q\le30 7
2 n,q≤100n,q\le100 23
3 所有瓷砖类型相同 15
4 无 55

样例 1

输入:

2 3
AB
AB
00
00
11
00
11
11
11
11
10
10
00
11

输出:

YES
NO
YES