题目描述

$N$ 个人站在一个圆圈，按逆时针顺序编号为 Snuke $1$，Snuke $2$，$\cdots$，Snuke $N$。

当 Snuke $i(1\le i\le N)$ 在时间 $t$ 收到一颗宝石时，它会在 $t+S_i$ 时间将该宝石交给 Snuke $i+1$。这里 Snuke $N+1$ 就是 Snuke $1$。此外，小高会在时间 $T_i$ 时给 Snuke $i$ 一颗宝石。

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

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $S_1,S_2,\cdots, S_N$。

第三行输入 $N$ 个整数 $T_1,T_2,\cdots,T_N$。

输出格式

输出 $N$ 行。第 $i$ 行（$1\le i \le N$）在应包含 Snuke $i$ 第一次收到宝石的时间。

输入输出样例 #1

输入 #1

3
4 1 5
3 10 100

输出 #1

3
7
8

输入输出样例 #2

输入 #2

4
100 100 100 100
1 1 1 1

输出 #2

1
1
1
1

输入输出样例 #3

输入 #3

4
1 2 3 4
1 2 4 7

输出 #3

1
2
4
7

输入输出样例 #4

输入 #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

说明/提示

样例 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$