Problem Statement

$N$ people stand in a row on a straight line.

The $i$-th person from the left is at position $X_i$ and can throw a ball, without a bounce, a distance of exactly $A_i$ to the left or right.

Each of the $N$ people throws a ball without moving from their fixed position and measures the distance the ball travels until it lands on the ground.

A distance traveled to the right is positive, and a distance traveled to the left is negative. They want to throw the ball as far as possible in the positive direction.

Having twisted the rules, the $N$ people decided to extend the distance as follows: if there is a person at the position where the ball lands, that person catches it and throws it again.

Under the twisted rules, find the maximum distance each of the $N$ people can throw, expressed as the maximum distance in the positive direction from the position of the $i$-th person.

Input

$N$
$X_1$ $X_2$ $\ldots$ $X_N$
$A_1$ $A_2$ $\ldots$ $A_N$

Constraints

• $ 1 \le N \le 2\times10^{5}$
• $ 0 \le X_i \le 10^{9}$
• $X_1 \lt X_2 \lt \ldots \lt X_N$
• $ 1 \le A_i \le 10^{9}$
• All input values are integers.

Output

Print $N$ lines.

On the $i$-th line, print the maximum distance for the $i$-th person from the left.

Print a newline at the end.

Sample

4
0 2 3 4
2 9 5 2

11
9
5
7

7
3 14 15 92 653 5897 9323
10 10 10 10 10 10 10

10
10
10
10
10
10
10

10
0 5 7 10 15 20 25 30 35 40 
5 5 8 20 10 20 25 10 40 10

50
45
43
40
35
30
25
20
40
10