B. Flip the Bits

B. Flip the Bits

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

For example, suppose a=0111010000a=0111010000.

• In the first operation, we can select the prefix of length 88 since it has four 00's and four 11's: [01110100]00→[10001011]00[01110100]00→[10001011]00.
• In the second operation, we can select the prefix of length 22 since it has one 00 and one 11: [10]00101100→[01]00101100[10]00101100→[01]00101100.
• It is illegal to select the prefix of length 44 for the third operation, because it has three 00's and one 11.

Can you transform the string aa into the string bb using some finite number of operations (possibly, none)?

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤3⋅1051≤n≤3⋅105) — the length of the strings aa and bb.

The following two lines contain strings aa and bb of length nn, consisting of symbols 00 and 11.

The sum of nn across all test cases does not exceed 3⋅1053⋅105.

Output

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

Example

input

Copy

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

output

Copy

YES
YES
NO
YES
NO

Note

The first test case is shown in the statement.

In the second test case, we transform aa into bb by using zero operations.

In the third test case, there is no legal operation, so it is impossible to transform aa into bb.

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

• Select the length 22 prefix to get 100101010101100101010101.
• Select the length 1212 prefix to get 011010101010011010101010.
• Select the length 88 prefix to get 100101011010100101011010.
• Select the length 44 prefix to get 011001011010011001011010.
• Select the length 66 prefix to get 100110011010100110011010.

In the fifth test case, the only legal operation is to transform aa into 111000111000. From there, the only legal operation is to return to the string we started with, so we cannot transform aa into bb.

只能翻转前缀是突破口，既然从头开始翻转，那么我们就可以从最后开始匹配，这样匹配完一个再匹配下一个的时候不会产生影响，只需要记录当前翻转次数，当前位置相等的时候，翻转次数是偶数那匹配成功，如果是奇数那么还需要保证本次能够反转成偶数，也就是前缀和的二倍等于当前位置。同理两者不等的时候也是如此。很精巧的一个好题

#include 
#include 
#include 
#include 
#include 
#include 
 
using namespace std;
typedef long long ll;
 
int sum[300000+10];
char s[300000+10],t[300000+10];
 
int main()
{
 
    int tt;
 
    cin>>tt;
 
    while(tt--)
    {
        int len;
 
        cin>>len;
 
        scanf("%s",s+1);
 
        scanf("%s",t+1);
 
        for(int i=1; i<=len; i++)
        {
            sum[i]=sum[i-1]+(s[i]=='1');
 
 
        }
 
        int nowcnt=0;
        int flag=0;
        for(int i=len; i>=1; i--)
        {
            if(s[i]==t[i])
            {
                if(nowcnt%2==0)
                {
                    continue;
                }
 
                else
                {
                    if(sum[i]*2!=i)
                    {
                        flag=1;
                        break;
                    }
                    else
                    {
                        nowcnt++;
                    }
                }
            }
            else if(s[i]!=t[i])
            {
                if(nowcnt%2)
                {
                    continue;
                }
                else
                {
                    if(sum[i]*2!=i)
                    {
                        flag=1;
                        break;
                    }
                    else
                    {
                        nowcnt++;
                    }
                }
            }
 
        }
 
        if(flag)
        {
            cout<<"NO"<
        }
        else
        {
            cout<<"YES"<
        }
    }
    return 0;
}