Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Flip the Bits

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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)?

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).

Example

Input

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

Output

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$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2021 19:21:20 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|