分数: 300 点
问题陈述
有 N 生物站成一圈,称为 Snuke 1, 2, ..., N 按逆时针顺序。
当潜射时 i (1 \leq i \leq N) 在某个时间收到宝石 t, S_i 单位时间后,它会将宝石交给Snuke i+1 时间 t+S_i。在这里,斯努克 N+1 是 Snuke 1.
另外,高桥将把一颗宝石交给 Snuke i 时间 T_i.
对于每个 i (1 \leq i \leq N),找到 Snuke 的时间 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) 应该包含 Snuke 的时间 i 第一次收到宝石。
示例输入 1
3 4 1 5 3 10 100
示例输出 1
3 7 8
我们将列出三名 Snuke 和 Takahashi 的最新行动 13 按时间顺序排列。
时间 3: 高桥将一颗宝石递给 Snuke 1.
时间 7:潜伏 1 将一颗宝石递给 Snuke 2.
时间 8:潜伏 2 将一颗宝石递给 Snuke 3.
时间 10: 高桥将一颗宝石递给 Snuke 2.
时间 11:潜伏 2 将一颗宝石递给 Snuke 3.
时间 13:潜伏 3 将一颗宝石递给 Snuke 1.
之后,他们将继续交出宝石,尽管这与答案无关。
示例输入 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
请注意,Snuke 可以同时执行多个事务。特别是,一个 Snuke 可能会同时从 Takahashi 和另一个 Snuke 那里收到宝石。
示例输入 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