Distribution

题目描述

有 $N$ 个生物站成一个圆圈，按逆时针顺序分别称为 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$。 此外，Takahashi 会在时间 $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

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 \leq N \leq 200000$ $1 \leq S_i,T_i \leq 10^9$ 输入中的所有数值均为整数。我们将按时间顺序列出三个 Snuke 和 Takahashi 在时间 $13$ 之前的动作。 时间 $3$：Takahashi 把一颗宝石交给 Snuke $1$。 时间 $7$：Snuke $1$ 把一颗宝石交给 Snuke $2$。 时间 $8$：Snuke $2$ 把一颗宝石交给 Snuke $3$。 时间 $10$：Takahashi 把一颗宝石交给 Snuke $2$。 时间 $11$：Snuke $2$ 把一颗宝石交给 Snuke $3$。 时间 $13$：Snuke $3$ 把一颗宝石交给 Snuke $1$。 之后他们会继续传递宝石，但这对答案无关紧要。
注意 $S_i$ 和 $T_i$ 的取值可能不互不相同。
注意一个 Snuke 可能同时执行多次交易。特别地，一个 Snuke 可能同时从 Takahashi 和另一个 Snuke 收到宝石。

标签: AtCoder|abc214C

来源

AtCoder|abc214C