Problem Description

Given two integer sequences of length $N$, $A_0, A_1, \cdots, A_{N-1}$ and $B_0, B_1, \cdots, B_{N-1}$, solve the following problem for all $k$ ($2 \leq k \leq N$).

• Construct an integer sequence $C_0, C_1, \cdots, C_{k-1}$. For all $i$ ($0 \leq i \leq k-1$), $C_i$ must satisfy $A_i \leq C_i \leq B_i$. What is the minimum possible value of the maximum of $C_{i+1} - C_i$ ($0 \leq i \leq k-2$)?

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_0 $ $ A_1 $ $\cdots$ $ A_{N-1} $ $ B_0 $ $ B_1 $ $\cdots$ $ B_{N-1} $

Output Format

Output $N-1$ lines. The $i$th ($1 \leq i \leq N-1$) line should contain the answer to the problem when $k = i+1$.

Sample Input and Output

Sample Input #1

4
0 0 1 2
2 1 3 3

Sample Output #1

-2
0
1

Sample Input #2

10
24 8 6 8 13 25 4 1 4 7
100 89 65 46 66 58 22 16 11 10

Sample Output #2

-92
-47
-30
-21
-10
-10
-10
-8
-4

Notes/Hints

Constraints

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

Sample Explanation 1

For each $k$, an example of the integer sequence $C$ that minimizes the maximum of $C_{i+1} - C_i$ is shown below:
- $k=2$: $C=(2,0)$
- $k=3$: $C=(1,1,1)$
- $k=4$: $C=(1,1,1,2)$

见题面 Input 部分

见题面 Output 部分