Score : $800$ points

Problem Statement

There are $N$ positive integers arranged in a circle.

Now, the $i$-th number is $A_i$. Takahashi wants the $i$-th number to be $B_i$. For this objective, he will repeatedly perform the following operation:

• Choose an integer $i$ such that $1 \leq i \leq N$.
• Let $a, b, c$ be the $(i-1)$-th, $i$-th, and $(i+1)$-th numbers, respectively. Replace the $i$-th number with $a+b+c$.

Here the $0$-th number is the $N$-th number, and the $(N+1)$-th number is the $1$-st number.

Determine if Takahashi can achieve his objective. If the answer is yes, find the minimum number of operations required.

Constraints

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $...$ $A_N$

$B_1$ $B_2$ $...$ $B_N$

Output

Print the minimum number of operations required, or -1 if the objective cannot be achieved.

3
1 1 1
13 5 7

4

Takahashi can achieve his objective by, for example, performing the following operations:

• Replace the second number with $3$.
• Replace the second number with $5$.
• Replace the third number with $7$.
• Replace the first number with $13$.

4
1 2 3 4
2 3 4 5

-1

5
5 6 5 2 1
9817 1108 6890 4343 8704

25