#227 Yet Another XOR Problem

Loading problem...

Preparing the statement, recent submissions, and submit form.

#227 Yet Another XOR Problem | DOJ

Authors: fldyof

Time limit: 1000 ms
Python time limit: 3000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

KO EN

You are given two integer arrays $A$ and $B$ of length $N$ .

You may perform the following operation on array $A$ any number of times.

Choose an integer $i$ such that $2 \leq i \leq N-1$ . Then replace $A_i$ with $A_{i-1} \oplus A_i \oplus A_{i+1}$ , where $\oplus$ denotes bitwise XOR.

Determine whether array $A$ can be made equal to array $B$ .

Input

The input is given in the following format.

$T$ $N$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_N$ $\vdots$

The first line contains the number of test cases $T$ . Each test case consists of $N$ , array $A$ , and array $B$ in this order.

Output

For each test case, print YES if array $A$ can be made equal to array $B$ , and print NO otherwise.

Constraints

$1 \leq T \leq 5\ 000$ .
$3 \leq N \leq 200\ 000$ .
$0 \leq A_i, B_i < 2^{30}$ ( $1 \leq i \leq N$ ).
The sum of $N$ over all test cases does not exceed $200\ 000$ .

Subtasks

#	Score	Constraints
1	12	$N=3$ .
2	23	The sum of $N$ over all test cases does not exceed $2\ 000$ .
3	65	There are no additional constraints.

Samples

Input

Output

YES
YES
NO
NO

In the first test case, choosing $i=2$ once changes the array to $[1,0,3]$ .

In the second test case, choosing $i=2$ once changes the array to $[1,7,4,8]$ .

Editorial

View editorial