問題文

$N$ 人のすぬけ君が円周上に並んでおり、反時計回りに $1,2,...,N$ の番号がついています。

$i\\, (1 \\leq i \\leq N)$ 番目のすぬけ君は時刻 $t$ に宝石をもらうと $S_i$ 単位時間後、すなわち時刻 $t+S_i$ にその宝石を $(i+1)$ 番目のすぬけ君に渡します。ただし、$(N+1)$ 番目のすぬけ君とは $1$ 番目のすぬけ君のことを指すとします。

また、高橋君は時刻 $T_i$ に $i$ 番目のすぬけ君に宝石を渡します。

全ての $i\\, (1 \\leq i \\leq N)$ について、$i$ 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

• $1 \\leq N \\leq 200000$
• $1 \\leq S_i,T_i \\leq 10^9$
• 入力は全て整数である。

---

入力

入力は以下の形式で標準入力から与えられる。

$N$ $S_1$ $S_2$ $\\ldots$ $S_N$ $T_1$ $T_2$ $\\ldots$ $T_N$

出力

$N$ 行出力せよ。$i\\, (1 \\leq i \\leq N)$ 行目には、$i$ 番目のすぬけ君が初めて宝石をもらう時刻を出力すること。

---

入力例 1

3
4 1 5
3 10 100

出力例 1

3
7
8

時刻 $13$ までのすぬけ君と高橋君の行動を時系列順に並べます。

時刻 $3$ : 高橋君が $1$ 番目のすぬけ君に宝石を渡します。

時刻 $7$ : $1$ 番目のすぬけ君が $2$ 番目のすぬけ君に宝石を渡します。

時刻 $8$ : $2$ 番目のすぬけ君が $3$ 番目のすぬけ君に宝石を渡します。

時刻 $10$ : 高橋君が $2$ 番目のすぬけ君に宝石を渡します。

時刻 $11$ : $2$ 番目のすぬけ君が $3$ 番目のすぬけ君に宝石を渡します。

時刻 $13$ : $3$ 番目のすぬけ君が $1$ 番目のすぬけ君に宝石を渡します。

時刻 $14$ 以降も彼らは宝石の受け渡しを行いますが、答えには影響しません。

---

入力例 2

4
100 100 100 100
1 1 1 1

出力例 2

1
1
1
1

$S_i$ や $T_i$ が相異なるとは限らないことに注意してください。

---

入力例 3

4
1 2 3 4
1 2 4 7

出力例 3

1
2
4
7

あるすぬけくんが同時刻に複数の宝石の受け渡しをする可能性があること、特に高橋くんとすぬけくんの両方から同時に宝石を貰う可能性があることに注意してください。

---

入力例 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

出力例 4

50
22
63
28
44
60
64
27