102704: [AtCoder]ABC270 E - Apple Baskets on Circle

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 

问题描述

有编号为$1, 2, \ldots, N$的篮子排成一个圆圈。
对于每个$1\leq i \leq N-1$，篮子$i+1$在篮子$i$的正右侧，篮子$1$在篮子$N$的正右侧。

篮子$i$现在有$A_i$个苹果。

Takahashi从篮子$1$的前面开始，并重复以下动作。

• 如果他面对的篮子中有苹果，就拿一个吃掉。然后，无论他现在是否吃了苹果，都继续走到下一个正右侧的篮子。

当Takahashi总共吃了$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$个整数应为当Takahashi总共吃了$K$个苹果时，篮子$i$中剩余的苹果数。

样例输入1

3 3
1 3 0

样例输出1

0 1 0 

Takahashi会进行以下操作。

• 他面对的篮子$1$中有苹果，所以他拿一个吃掉。然后，他继续走到篮子$2$。现在，篮子中有$0,3,0$个苹果。
• 他面对的篮子$2$中有苹果，所以他拿一个吃掉。然后，他继续走到篮子$3$。现在，篮子中有$0,2,0$个苹果。
• 他面对的篮子$3$中没有苹果。然后，他继续走到篮子$1$。现在，篮子中有$0,2,0$个苹果。
• 他面对的篮子$1$中没有苹果。然后，他继续走到篮子$2$。现在，篮子中有$0,2,0$个苹果。
• 他面对的篮子$2$中有苹果，所以他拿一个吃掉。然后，他继续走到篮子$3$。现在，篮子中有$0,1,0$个苹果。

样例输入2

2 1000000000000
1000000000000 1000000000000

样例输出2

500000000000 500000000000