/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,...,N の番号がついています。
i\, (1 \leq i \leq N) 番目のすぬけ君は時刻 t に宝石をもらうと S_i 単位時間後、すなわち時刻 t+S_i にその宝石を (i+1) 番目のすぬけ君に渡します。ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。
また、高橋君は時刻 T_i に i 番目のすぬけ君に宝石を渡します。
全ての i\, (1 \leq i \leq N) について、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) 行目には、i 番目のすぬけ君が初めて宝石をもらう時刻を出力すること。
入力例 1
3 4 1 5 3 10 100
出力例 1
3 7 8
時刻 13 までのすぬけ君と高橋君の行動を時系列順に並べます。
時刻 3 : 高橋君が 1 番目のすぬけ君に宝石を渡します。
時刻 7 : 1 番目のすぬけ君が 2 番目のすぬけ君に宝石を渡します。
時刻 8 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。
時刻 10 : 高橋君が 2 番目のすぬけ君に宝石を渡します。
時刻 11 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。
時刻 13 : 3 番目のすぬけ君が 1 番目のすぬけ君に宝石を渡します。
時刻 14 以降も彼らは宝石の受け渡しを行いますが、答えには影響しません。
入力例 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
あるすぬけくんが同時刻に複数の宝石の受け渡しをする可能性があること、特に高橋くんとすぬけくんの両方から同時に宝石を貰う可能性があることに注意してください。
入力例 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
Score : 300 points
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