問題文

直線上に $N$ 人が一列に並んでいます。

左から $i$ 番目の人は位置 $X_i$ にいて、左右にちょうど $A_i$ の距離、ノーバウンドでボールを投げられます。

$N$ 人はそれぞれの定位置から動かずにボールを投げ、ボールが地面に落ちるまでの距離を測ります。

右側へ飛んだ距離を正とし、左側に飛んだ距離を負とします。出来る限り正の遠い距離にボールを投げたいです。

ルールを曲解した $N$ 人は、ボールの落下位置に人がいればキャッチしてもらい、その位置の人にまた投げてもらうことで距離を伸ばすことにしました。

曲解したルールで、$N$ 人はそれぞれ最大どのくらい遠い距離に投げられるか、$i$ 番目の位置からの正の方向への最大距離で答えてください。

入力

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

制約

• $ 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}$
• 入力は全て整数

出力

$N$ 行出力してください。

$i$ 行目には、左から $i$ 番目の人の最大距離を出力してください。

最後に改行してください。

サンプル

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