codeforces#P1504B. Flip the Bits

    ID: 31918 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>constructive algorithmsgreedyimplementationmath*1200

Flip the Bits

Description

There is a binary string $a$ of length $n$. In one operation, you can select any prefix of $a$ with an equal number of $0$ and $1$ symbols. Then all symbols in the prefix are inverted: each $0$ becomes $1$ and each $1$ becomes $0$.

For example, suppose $a=0111010000$.

  • In the first operation, we can select the prefix of length $8$ since it has four $0$'s and four $1$'s: $[01110100]00\to [10001011]00$.
  • In the second operation, we can select the prefix of length $2$ since it has one $0$ and one $1$: $[10]00101100\to [01]00101100$.
  • It is illegal to select the prefix of length $4$ for the third operation, because it has three $0$'s and one $1$.

Can you transform the string $a$ into the string $b$ using some finite number of operations (possibly, none)?

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 3\cdot 10^5$) — the length of the strings $a$ and $b$.

The following two lines contain strings $a$ and $b$ of length $n$, consisting of symbols $0$ and $1$.

The sum of $n$ across all test cases does not exceed $3\cdot 10^5$.

For each test case, output "YES" if it is possible to transform $a$ into $b$, or "NO" if it is impossible. You can print each letter in any case (upper or lower).

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 3\cdot 10^5$) — the length of the strings $a$ and $b$.

The following two lines contain strings $a$ and $b$ of length $n$, consisting of symbols $0$ and $1$.

The sum of $n$ across all test cases does not exceed $3\cdot 10^5$.

Output

For each test case, output "YES" if it is possible to transform $a$ into $b$, or "NO" if it is impossible. You can print each letter in any case (upper or lower).

Samples

5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100
YES
YES
NO
YES
NO

Note

The first test case is shown in the statement.

In the second test case, we transform $a$ into $b$ by using zero operations.

In the third test case, there is no legal operation, so it is impossible to transform $a$ into $b$.

In the fourth test case, here is one such transformation:

  • Select the length $2$ prefix to get $100101010101$.
  • Select the length $12$ prefix to get $011010101010$.
  • Select the length $8$ prefix to get $100101011010$.
  • Select the length $4$ prefix to get $011001011010$.
  • Select the length $6$ prefix to get $100110011010$.

In the fifth test case, the only legal operation is to transform $a$ into $111000$. From there, the only legal operation is to return to the string we started with, so we cannot transform $a$ into $b$.