Under construction

Still being built. Things may change

Button Pressing

Time limit2sMemory limit1024 MB

Summary
Given initial lamp states A and target states B, decide whether pressing buttons that flip neighboring lamps (only when the button's own lamp is on) can reach B.
Level

Medium5 of 10

Topics
String, Greedy, Simulation
Solved
No attempts yet

Problem

You are given NN buttons (numbered from 11 to NN) and NN lamps (numbered from 11 to NN). Each lamp can be either on or off. Initially, lamp ii is on if Ai=1A_i = 1, and off if Ai=0A_i = 0.

Button ii is connected to lamp i−1i - 1 (if i>1i > 1) and lamp i+1i + 1 (if i<Ni < N). In one move, you can press button ii only if lamp ii is on. When a button is pressed, the state of the lamps connected to it is toggled: a lamp that was off turns on, and a lamp that was on turns off. Button ii is not connected to lamp ii, so pressing button ii does not change the state of lamp ii.

After zero or more moves, you want lamp ii to be on if Bi=1B_i = 1, and off if Bi=0B_i = 0. Determine whether this is possible.

Input

The first line contains an integer TT (1≤T≤10001 \le T \le 1000), the number of test cases. Each test case consists of three lines.

The first line of each test case contains an integer NN (3≤N≤2000003 \le N \le 200000). The sum of NN over all test cases does not exceed 200000.

The second line contains a string AA of length NN. Each character is 0 or 1. The ii-th character is the initial state of lamp ii.

The third line contains a string BB of length NN. Each character is 0 or 1. The ii-th character is the desired final state of lamp ii.

Output

For each test case, print YES on a single line if all lamps can be brought to their desired states, or NO otherwise.

Examples2

  1. Example 1

    Input
    2
    4
    0101
    0100
    3
    000
    010
    
    Expected output
    YES
    NO
    
  2. Example 2

    Input
    5
    7
    0101011
    1111010
    5
    11111
    00000
    4
    1101
    1101
    6
    101010
    100100
    3
    000
    000
    
    Expected output
    NO
    NO
    YES
    YES
    YES