Adjacent Transformations - Repovive Premier Round 10 | Repovive

30G. Adjacent Transformations

3500 pts1s256 MB

You are given two integer arrays $a$ and $b$ , each of length $n$ .

In one operation, choose two adjacent entries of $a$ and apply one of these rules:

For integers $x<y$ , $(x,y)\longleftrightarrow(y+1,x+1).$ This rule can be applied in either direction.
For any integer $x$ , $(x,x)\longrightarrow(x-1,x).$ This rule can be applied only in the displayed direction.

Operations may be repeated, and intermediate entries may be any integers.

Determine whether $a$ can be transformed into $b$ using zero or more operations. Output Yes if it can, and No otherwise.

Constraints

$1 \le t \le 10^4$ .
$1 \le n \le 2 \times 10^5$ .
$-n \le a_i,b_i \le n$ for every $1 \le i \le n$ .
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ b_1 \quad b_2 \quad \ldots \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{Yes} \; / \; \text{No} \end{array} \right\} \times t

Yes and No are case-insensitive.

Samples

Input

Case 1

1
0
0

Case 2

2
0 1
2 1

Case 3

2
2 1
0 1

Case 4

2
-2 -2
-1 -2

Case 5

2
-1 0
0 0

Case 6

1
0
1

Explanation

Case 1

The arrays are already equal, so zero operations suffice.

Case 2

Apply the first rule to obtain $(0,1)\longrightarrow(2,1)$ .

Case 3

Apply the first rule in reverse to obtain $(2,1)\longrightarrow(0,1)$ .

Case 4

First break the equality, then use the first rule: $(-2,-2)\longrightarrow(-3,-2)\longrightarrow(-1,-2)$ . The intermediate value $-3$ is allowed.

Case 5

With two unequal entries, the first rule keeps them unequal, and the second rule cannot be applied. Therefore the equal target cannot be reached.

Case 6

There is only one entry, so no operation can change it.

Output

Case 1

Yes

Case 2

Yes

Case 3

Yes

Case 4

Yes

Case 5

No

Case 6

No

You are given two integer arrays $a$ and $b$ , each of length $n$ .

In one operation, choose two adjacent entries of $a$ and apply one of these rules:

For integers $x<y$ , $(x,y)\longleftrightarrow(y+1,x+1).$ This rule can be applied in either direction.
For any integer $x$ , $(x,x)\longrightarrow(x-1,x).$ This rule can be applied only in the displayed direction.

Operations may be repeated, and intermediate entries may be any integers.

Determine whether $a$ can be transformed into $b$ using zero or more operations. Output Yes if it can, and No otherwise.

$1 \le t \le 10^4$ .
$1 \le n \le 2 \times 10^5$ .
$-n \le a_i,b_i \le n$ for every $1 \le i \le n$ .
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ b_1 \quad b_2 \quad \ldots \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{Yes} \; / \; \text{No} \end{array} \right\} \times t

Yes and No are case-insensitive.

Apply the first rule to obtain $(0,1)\longrightarrow(2,1)$ .

Apply the first rule in reverse to obtain $(2,1)\longrightarrow(0,1)$ .

First break the equality, then use the first rule: $(-2,-2)\longrightarrow(-3,-2)\longrightarrow(-1,-2)$ . The intermediate value $-3$ is allowed.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

30G. Adjacent Transformations

Constraints

Input

Output

Samples

30G. Adjacent Transformations

Constraints

Input

Output

Samples