你有一个管道系统。它由两行组成,每行由 $$$n$$$ 管道组成。左上角管道的坐标为 $$$(1, 1)$$$,右下角管道的坐标为 $$$(2, n)$$$。
管道有六种类型:两种直管和四种弯管。以下是所有六种类型的示例:
管道类型
您可以将每个给定的管道顺时针或逆时针旋转 $$$90$$$ 度任意(可能为零)次数(因此类型 $$$1$$$ 和 $$$2$$$ 可以相互转换,并且类型 $$$3, 4, 5, 6$$$ 可以相互转换)。
您想要以某种方式转动一些管道,使水流可以从 $$$(1, 0)$$$(左上角管道的左侧)开始,移动到 $$$(1, 1)$$$ 处的管道,通过连接的管道以某种方式流到 $$$(2, n)$$$ 处的管道,然后向右流到 $$$(2, n + 1)$$$。
如果管道在系统中相邻并且其末端已连接,则管道已连接。以下是连接管道的示例:
连接管道示例
让我们用一些例子来描述这个问题:
第一个示例输入
其解决方案如下:
第一个示例答案
如您所见,水流是画得不好的蓝线。为了获得答案,我们需要顺时针转动 $$$(1, 2)$$$ $$$90$$$ 度的管道、$$$(2, 3)$$$ $$$90$$$ 度的管道、$$$(1, 6)$$$ $$$90$$$ 度的管道、$$$(1, 7)$$$ $$$180$$$ 度的管道以及$$$(2, 7)$$$ $$$180$$$ 度。那么水流可以从$$$(1, 0)$$$到达$$$(2, n + 1)$$$。
您必须回答 $$$q$$$ 独立查询。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^4$$$) — 查询数。然后是 $$$q$$$ 查询。
每个查询仅由三行组成。查询的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 每行中的管道数量。接下来的两行相应地包含第一行和第二行的描述。每行描述由 $$$n$$$ 数字组成,从 $$$1$$$ 到 $$$6$$$ 之间没有任何空格,每个数字对应于相应单元格中的管道类型。请参阅问题陈述以了解哪些数字对应于哪些类型的管道。
保证所有查询的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于第 $$$i$$$ 查询,打印答案 — 如果可以以水流从 $$$(1, 0)$$$ 到达 $$$(2, n + 1)$$$ 的方式转动某些管道,则打印“是”(不带引号),否则为“否”。
示例
输入 #1
6 7 2323216 1615124 1 3 4 2 13 24 2 12 34 3 536 345 2 46 54
输出 #1
YES YES YES NO YES NO
注意
示例中的第一个查询在问题陈述中进行了描述。