宝石的传递

题目描述

有 $N$ 只名为 Snuke 的生物按逆时针方向围成一圈,记为 Snuke $1, 2, ..., N$。

当 Snuke $i$($1 \leq i \leq N$)在时刻 $t$ 收到宝石时,它会在 $S_i$ 个单位时间后,即在时刻 $t+S_i$,把宝石交给 Snuke $i+1$。这里,Snuke $N+1$ 就是 Snuke $1$。

另外,高桥君会在时刻 $T_i$ 给 Snuke $i$ 递一颗宝石。

对于每个 $i$($1 \leq i \leq N$),求 Snuke $i$ 第一次收到宝石的时刻。假设传递宝石所需的时间可以忽略不计。

输入格式

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

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

输出格式

输出 $N$ 行。第 $i$ 行($1 \leq i \leq N$)输出 Snuke $i$ 第一次收到宝石的时刻。

样例

3
4 1 5
3 10 100

3
7
8

下面按时间顺序列出到时刻 $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$。

此后它们还会继续传递宝石,不过这已与答案无关。

4
100 100 100 100
1 1 1 1

1
1
1
1

注意,$S_i$ 和 $T_i$ 的值可能不互不相同。

4
1 2 3 4
1 2 4 7

1
2
4
7

注意,一只 Snuke 可能同时进行多次传递。特别是,一只 Snuke 可能同时从高桥君和另一只 Snuke 那里收到宝石。

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 \le N \le 200000$
• $1 \le S_i,T_i \le 10^9$
• 输入均为整数