题目描述

$N$个人站成一个圆圈，按逆时针顺序编号为Snuke $1$,Snuke $2$, ...,Snuke $N$。当Snuke $i (1 ≤ i ≤ N)$ 在时间$t$收到一颗宝石时，它会在$t+S_i$时间将该宝石交给Snuke $i+1$。这里，Snuke $N+1$就是Snuke $1$。此外，小高会在时间$T_i$时给Snuke $i$一颗宝石。

对于每个$i (1 ≤ i ≤ N)$，找出Snuke $i$第一次收到宝石的时间。假设交接宝石的时间可以忽略不计。

输入格式

输入从标准输入中以下列格式给出：

$N$

$S_1$ $S_2$ ... $S_N$

$T_1$ $T_2$ ... $T_N$

输出格式

输出$N$行。第$i$行$(1 ≤ i ≤ N)$应包含Snuke $i$第一次收到宝石的时间。

样例

3
4 1 5
3 10 100

3
7
8

4
100 100 100 100
1 1 1 1

1
1
1
1

4
1 2 3 4
1 2 4 7

1
2
4
7

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

50
22
63
28
44
60
64
27

样例解释

【样例1说明】
下面按时间顺序列出时间13之前小高和Snuke之间的行动。

时间3：小高给Snuke $1$一颗宝石。
时间7：Snuke $1$给Snuke $2$一颗宝石。
时间8：Snuke $2$给Snuke $3$一颗宝石。
时间10：小高给Snuke $2$一颗宝石。
时间11：Snuke $2$给Snuke $3$一颗宝石。
时间13：Snuke $3$给Snuke $1$一颗宝石。

之后，他们会继续传递宝石，尽管这与答案无关。
【样例2说明】
注意$S_i$和$T_i$的值可能不是唯一的。
【样例3说明】
注意一个Snuke可能同时进行多个交易。特别是，一个Snuke可能同时从小高和另一个Snuke那里收到宝石。

数据范围

• $1 ≤ N ≤ 200000$
• $1 ≤ S_i,T_i ≤ 10^9$
• 所有输入值都是整数。

来源

• AtCoder ABC214C