C. c0=c1
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two binary sequences $$$a,b$$$ with size $$$n$$$,and two intervals $$$[x_1, y_1],[x_2, y_2]$$$.

Define:

$$$c0(t,l,r)$$$ — the number of $$$0$$$ in $$$t_l,t_{l+1},...,t_r$$$.

$$$c1(t,l,r)$$$ — the number of $$$1$$$ in $$$t_l,t_{l+1},...,t_r$$$.

Find whether there are two intervals $$$[l_1,r_1],[l_2,r_2]$$$ satisfying all the following conditions:

  1. $$$x_1 \leq r_1-l_1+1 \leq y_1$$$.
  2. $$$x_2 \leq r_2-l_2+1 \leq y_2$$$.
  3. $$$c0(a,l_1,r_1)+c0(b,l_2,r_2)=c1(a,l_1,r_1)+c1(b,l_2,r_2)$$$.
Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line of each test case contains five space-separated integers $$$n,x_1,y_1,x_2,y_2(1 \leq n \leq 2*10^5,1 \leq x_1 \leq y_1 \leq n,1 \leq x_2 \leq y_2 \leq n)$$$.

The second line contains $$$n$$$ space-separated integers:$$$a_1$$$,$$$a_2$$$,...$$$a_n$$$ $$$(0 \leq a_i \leq 1)$$$.

The third line contains $$$n$$$ space-separated integers:$$$b_1$$$,$$$b_2$$$,...$$$b_n$$$ $$$(0 \leq b_i \leq 1)$$$.

The sum of $$$n$$$ over all test cases won't exceed $$$2*10^5$$$.

Output

For each test case, output on a new line — if there are two interval $$$[l_1,r_1],[l_2,r_2]$$$ satisfying the conditions,output $$$YES$$$,otherwise output $$$NO$$$.

Example
Input
4
4 3 3 3 3
0 1 0 1
0 1 0 0
5 4 5 1 3
1 1 1 1 1
0 0 0 0 1
4 2 4 1 3
1 1 1 1
0 1 1 0
6 1 2 1 2
0 0 0 0 0 0
0 0 0 1 0 0
Output
YES
NO
NO
YES
Note

Test case $$$1$$$:

All possible solutions are $$$[l_1,r_1]=[2,4],[l_2,r_2]=[1,3]$$$ and $$$[l_1,r_1]=[2,4],[l_2,r_2]=[2,4]$$$.

Test case $$$2$$$:

There does not exist any $$$[l_1,r_1],[l_2,r_2]$$$ satisfying all the conditions.

For example,$$$[l_1,r_1]=[1,4],[l_2,r_2]=[1,4]$$$ satisfy condition $$$1$$$ and $$$3$$$,but don't satisfy condition $$$2$$$.