Money Transfer

Problem Statement

In the Kingdom of JOI, there are N houses arranged around Beaver Lake and numbered 1 through N in counter‐clockwise order. From any house, you can send money to its immediate left neighbor. Specifically, for house i (1 ≤ i ≤ N−1) the left neighbor is house i+1, and for house N the left neighbor is house 1.

When a house sends a remittance, the transfer amount must be an integer, and a fee equal to the transfer amount is charged. In other words, if a house sends y units, it must pay a total of 2y units. At the moment of transfer, the sending house must have at least 2y units available. (Note that the fee is paid out of the house’s money and is not received by the destination house.)

You are given that initially house i has A_i units, and the desired amount is B_i units. Using only these transfers, determine whether it is possible to achieve the desired amounts in all houses. No other spending or depositing of money is allowed.

Modeling the Process

When a house i sends y_i units (where 0 ≤ y_i is an integer) to its left neighbor, its money decreases by 2y_i, and the left neighbor (house i+1, with house N+1 interpreted as house 1) receives y_i units. Therefore, after all transfers are complete, the money in house i becomes:

B_i = A_i - 2y_i + y_i-1

where indices are taken modulo N (with y₀ = y_N). Equivalently, the system of equations can be written as:

y_i-1 - 2y_i = B_i - A_i, for i = 1,2,…,N (with y₀ = y_N).

It can be shown that a necessary and sufficient condition for a solution in nonnegative integers y₁, …, y_N is that

\[ y_1 = \frac{\sum_{j=1}^{N}2^{N-j}(A_j - B_j)}{2^N-1} \]

is a nonnegative integer and, when computing subsequent values by

\[ y_{i+1} = \frac{y_i - (B_{i+1}-A_{i+1})}{2} \quad (1 \le i \le N-1), \]

each computed y_i is a nonnegative integer and the cyclic condition

\[ y_N - 2y_1 = B_1-A_1 \]

holds. (For the case N = 1, the equation simply gives y₁ = A₁ - B₁ and a solution is possible if and only if A₁ ≥ B₁.)

Input and Output

Your task is to determine whether it is possible to achieve the desired distribution B by a sequence of valid transfers.

inputFormat

The input is given in the following format:

N
A1 A2 ... AN
B1 B2 ... BN

Here, 1 ≤ N and all A_i and B_i are nonnegative integers.

outputFormat

Output a single line containing YES if it is possible to achieve the desired distribution, and NO otherwise.

sample

1
10
5

YES