Score : $300$ points

问题描述

有 $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$ 第一次收到宝石的时间。假设传递宝石所需的时间可以忽略不计。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ creatures standing in a circle, called Snuke $1, 2, ..., N$ in counter-clockwise order.

When Snuke $i$ $(1 \leq i \leq N)$ receives a gem at time $t$, $S_i$ units of time later, it will hand that gem to Snuke $i+1$ at time $t+S_i$. Here, Snuke $N+1$ is Snuke $1$.

Additionally, Takahashi will hand a gem to Snuke $i$ at time $T_i$.

For each $i$ $(1 \leq i \leq N)$, find the time when Snuke $i$ receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

• $1 \leq N \leq 200000$
• $1 \leq S_i,T_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$S_1$ $S_2$ $\ldots$ $S_N$

$T_1$ $T_2$ $\ldots$ $T_N$

Output

Print $N$ lines. The $i$-th line $(1 \leq i \leq N)$ should contain the time when Snuke $i$ receives a gem for the first time.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time $13$ in chronological order.

Time $3$: Takahashi hands a gem to Snuke $1$.

Time $7$: Snuke $1$ hands a gem to Snuke $2$.

Time $8$: Snuke $2$ hands a gem to Snuke $3$.

Time $10$: Takahashi hands a gem to Snuke $2$.

Time $11$: Snuke $2$ hands a gem to Snuke $3$.

Time $13$: Snuke $3$ hands a gem to Snuke $1$.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values $S_i$ and $T_i$ may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

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

Sample Output 4

50
22
63
28
44
60
64
27

update @ 2024/3/10 09:31:19