← 返回题目列表

Codeforces · 1994/B

B. 有趣的游戏

中文机器翻译题面 查看原题

Vova 非常喜欢 XOR 运算(表示为 $$$\oplus$$$)。最近,当他要睡觉的时候,他想出了一个有趣的游戏。

游戏开始时,Vova 选择长度为 $$$n$$$ 的两个二进制序列 $$$s$$$ 和 $$$t$$$ 并将它们交给 Vanya。二进制序列是仅由数字 $$$0$$$ 和 $$$1$$$ 组成的序列。 Vanya 可以选择整数 $$$l、r$$$,使得 $$$1 \leq l \leq r \leq n$$$,并且对于所有 $$$l \leq i \leq r$$$ 同时将 $$$s_i$$$ 替换为 $$$s_i \oplus s_{i - l + 1}$$$,其中 $$$s_i$$$ 是序列的第 $$$i$$$ 个元素$$$s$$$。

为了让游戏有趣,必须有获胜的可能性。如果 Vanya 在无限数量的操作下能够从序列 $$$s$$$ 中获得序列 $$$t$$$,则他获胜。确定游戏对于序列 $$$s$$$ 和 $$$t$$$ 是否有趣。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^{4}$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 序列 $$$s$$$ 和 $$$t$$$ 的长度。

每个测试用例的第二行包含长度为$$$n$$$的二进制序列$$$s$$$。

每个测试用例的第三行包含长度为$$$n$$$的二进制序列$$$t$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果游戏有趣,则输出“Yes”,否则输出“No”。

您可以在任何情况下输出每个字母(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

6
1
0
1
7
0110100
0110100
9
100101010
101111110
4
0011
1011
4
0100
0001
8
10110111
01100000

输出 #1

NO
YES
YES
NO
YES
YES

注意

在第一个测试用例中,Vanya 将无法通过选择 $$$l = r = 1$$$ 的唯一可能操作来更改序列 $$$s$$$。

在第二个测试用例中,序列 $$$s$$$ 和 $$$t$$$ 已经相等。

在第三个测试用例中,Vanya 可以执行以下操作:

1. 选择$$$l = 3$$$和$$$r = 5$$$,则$$$s$$$将变为$$$\mathtt{101101010}$$$。
2. 选择$$$l = 5$$$和$$$r = 6$$$,则$$$s$$$将变为$$$\mathtt{101111010}$$$。
3. 选择$$$l = 7$$$ 和$$$r = 7$$$,则$$$s$$$ 将变为$$$\mathtt{101111110}$$$。