/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1,2,\ldots,N の番号がついた N 個のかごが円状に置かれています。
1\leq i \leq N-1 についてかご i の右隣にはかご i+1 があり、かご N の右隣にはかご 1 があります。
かご i の中には A_i 個りんごが入っています。
高橋君は最初かご 1 の前におり、以下の行動を繰り返します。
- 目の前にあるかごの中にりんごがあれば 1 個かごから取り出して食べる。その後、りんごを食べたかどうかにかかわらず、右隣のかごの前に移動する。
高橋君がちょうど K 個のりんごを食べた時点で、各かごの中に残っているりんごの個数を求めてください。
制約
- 1 \leq N \leq 10^5
- 0 \leq A_i \leq 10^{12}
- 1 \leq K \leq 10^{12}
- りんごは全部で K 個以上ある。すなわち、\sum_{i=1}^{N}A_i\geq K
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
N 個の整数を空白区切りで出力せよ。
i 番目には、高橋君がちょうど K 個のりんごを食べた時点で、かご i の中に残っているりんごの個数を出力せよ。
入力例 1
3 3 1 3 0
出力例 1
0 1 0
高橋君は次のように行動します。
- 目の前にあるかご 1 の中にりんごがあるので 1 個かごから取り出して食べる。その後、かご 2 の前に移動する。この時点で各かごの中のりんごの個数は (0,3,0) である。
- 目の前にあるかご 2 の中にりんごがあるので 1 個かごから取り出して食べる。その後、かご 3 の前に移動する。この時点で各かごの中のりんごの個数は (0,2,0) である。
- 目の前にあるかご 3 の中にりんごはない。かご 1 の前に移動する。この時点で各かごの中のりんごの個数は (0,2,0) である。
- 目の前にあるかご 1 の中にりんごはない。かご 2 の前に移動する。この時点で各かごの中のりんごの個数は (0,2,0) である。
- 目の前にあるかご 2 の中にりんごがあるので 1 個かごから取り出して食べる。その後、かご 3 の前に移動する。この時点で各かごの中のりんごの個数は (0,1,0) である。
入力例 2
2 1000000000000 1000000000000 1000000000000
出力例 2
500000000000 500000000000
Score : 500 points
Problem Statement
There are N baskets numbered 1, 2, \ldots, N arranged in a circle.
For each 1\leq i \leq N-1, basket i+1 is to the immediate right of basket i, and basket 1 is to the immediate right of basket N.
Basket i now contains A_i apples.
Takahashi starts in front of basket 1 and repeats the following action.
- If the basket he is facing contains an apple, take one and eat it. Then, regardless of whether he has eaten an apple now, go on to the next basket to the immediate right.
Find the number of apples remaining in each basket when Takahashi has eaten exactly K apples in total.
Constraints
- 1 \leq N \leq 10^5
- 0 \leq A_i \leq 10^{12}
- 1 \leq K \leq 10^{12}
- There are at least K apples in total. That is, \sum_{i=1}^{N}A_i\geq K.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Print N integers, with spaces in between.
The i-th integer should be the number of apples remaining in basket i when Takahashi has eaten exactly K apples in total.
Sample Input 1
3 3 1 3 0
Sample Output 1
0 1 0
Takahashi will do the following.
- Basket 1, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 2. Now, the baskets have 0,3,0 apples.
- Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,2,0 apples.
- Basket 3, which he is facing, contains no apple. Then, he goes on to basket 1. Now, the baskets have 0,2,0 apples.
- Basket 1, which he is facing, contains no apple. Then, he goes on to basket 2. Now, the baskets have 0,2,0 apples.
- Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,1,0 apple(s).
Sample Input 2
2 1000000000000 1000000000000 1000000000000
Sample Output 2
500000000000 500000000000