題干：

Little Vasya had?n?boxes with balls in the room. The boxes stood in a row and were numbered with numbers from 1 to?n?from left to right.

Once Vasya chose one of the boxes, let's assume that its number is?i, took all balls out from it (it is guaranteed that this box originally had at least one ball), and began putting balls (one at a time) to the boxes with numbers?i?+?1,?i?+?2,?i?+?3?and so on. If Vasya puts a ball into the box number?n, then the next ball goes to box?1, the next one goes to box?2?and so on. He did it until he had no balls left in his hands. It is possible that Vasya puts multiple balls to the same box, and it is also possible that one or more balls will go to the box number?i. If?i?=?n, Vasya puts the first ball into the box number?1, then the next ball goes to box?2?and so on.

For example, let's suppose that initially Vasya had four boxes, and the first box had?3?balls, the second one had?2, the third one had?5?and the fourth one had?4balls. Then, if?i?=?3, then Vasya will take all five balls out of the third box and put them in the boxes with numbers:?4,?1,?2,?3,?4. After all Vasya's actions the balls will lie in the boxes as follows: in the first box there are?4?balls,?3?in the second one,?1?in the third one and?6?in the fourth one.

At this point Vasya has completely forgotten the original arrangement of the balls in the boxes, but he knows how they are arranged now, and the number?x?— the number of the box, where he put the last of the taken out balls.

He asks you to help to find the initial arrangement of the balls in the boxes.

Input

The first line of the input contains two integers?n?and?x?(2?≤?n?≤?105,?1?≤?x?≤?n), that represent the number of the boxes and the index of the box that got the last ball from Vasya, correspondingly. The second line contains?n?space-separated integers?a1,?a2,?...,?an, where integer?ai?(0?≤?ai?≤?109,?ax?≠?0) represents the number of balls in the box with index?i?after Vasya completes all the actions.

Please, do not use the?%lld?specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the?%I64d?specifier.

Output

Print?n?integers, where the?i-th one represents the number of balls in the box number?i?before Vasya starts acting. Separate the numbers in the output by spaces. If there are multiple correct solutions, you are allowed to print any of them.

Examples

Input

4 4 4 3 1 6

Output

3 2 5 4

Input

5 2 3 2 0 2 7

Output

2 1 4 1 6

Input

3 3 2 3 1

Output

1 2 3

題目大意：

? ?就是說(shuō)啊我有一堆放著球的盒子（但是可能有的盒子中沒(méi)有球），我們現(xiàn)在選擇一個(gè)有球的盒子，然后把里面的球全都拿出來(lái)并且給后面的分球，挨個(gè)分球（比如我從2號(hào)盒子拿出所有球來(lái)了，那么就從3號(hào)節(jié)點(diǎn)開(kāi)始分球，，4號(hào)，5號(hào)這樣，如果到頭了那就再回到1號(hào)盒子開(kāi)始分球）。現(xiàn)在給你了一共n個(gè)盒子，每個(gè)盒子在過(guò)程結(jié)束時(shí)的球數(shù)，以及是在最后發(fā)完球的時(shí)候是停在哪個(gè)盒子上了（也就是最后一個(gè)球是給的哪個(gè)盒子）。問(wèn)你這些盒子中的每個(gè)盒子最初由多少球在里面。

解題報(bào)告：

? ? 這題剛開(kāi)始就想著模擬，，，結(jié)果wa4了。。。其實(shí)就是倒著模擬整個(gè)過(guò)程就好了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll a[MAX]; int main() {ll n,x,tmp=0;cin>>n>>x;ll minn = 0x3f3f3f3f3f3f;for(int i = 1; i<=n; i++) scanf("%lld",a+i),minn = min(minn,a[i]);for(int i = 1; i<=n; i++) a[i] -= minn;while(a[x] != 0) {a[x]--;x--;tmp++;if(x==0) x=n;}a[x] = tmp + minn*n;for(int i = 1; i<=n; i++) printf("%lld%c",a[i],i == n ? '\n' : ' ');return 0 ;}

?

錯(cuò)誤代碼：（這個(gè)是真的不用看了，，面目全非了）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll a[MAX]; ll n,x; ll ans1[MAX],ans2[MAX]; bool ok(int i) { // ll up = a[i]; // n; // ll tmp = a[i] - up; // if(tmp % n + i == x) return 1; // else return 0;return 1; } int main() {int cnt1=0,cnt2=0;cin>>n>>x;x--;for(int i = 0; i<n; i++) cin>>a[i];//從0開(kāi)始讀入ll minn = 0x3f3f3f3f3f; for(int i = 0; i<n; i++) {if(a[i] < minn) {cnt1 = 0;ans1[++cnt1] = i;minn = a[i];}else if (a[i] == minn) {ans1[++cnt1] = i;}}ll minn2 = 0x3f3f3f3f3f;for(int i = 0; i<n; i++) {if(a[i] < minn2 && a[i] > minn) {cnt2=0;ans2[++cnt2] = i;minn2 = a[i];}else if(a[i] == minn2) {ans2[++cnt2] == i;}}int that=-1;//先遍歷最小for(int i = 1; i<=cnt1; i++) {if(ok(ans1[i])) {that = ans1[i];break;}}if(that != -1) {ll up = a[that];ll tmp = that <= x ? x-that : x+n-that;a[that]=0;a[that]-=tmp;for(int i = 0; i<n; i++) {if(i != that) a[i] -= up;else a[i] -= up*n;}for(int i = 1; i<=tmp; i++) {a[(that+i)%n]--;} for(int i = 0; i<n; i++) {printf("%lld%c",i == that ? -a[i] : a[i] , i == (n-1) ? '\n' : ' ');}return 0 ;}for(int i = 1; i<=cnt2; i++) {if(ok(ans2[i])) {that = ans2[i];break;}}ll up = a[that];ll tmp = that < x ? x-that : x+n-that;a[that]=0;a[that] -=tmp;for(int i = 0; i<n; i++) {if(i != that) a[i] -= up;else a[i] -= up*n;}for(int i = 1; i<=tmp; i++) {a[(that+i)%n]--;} for(int i = 0; i<n; i++) {printf("%lld%c",i == that ? -a[i] : a[i] , i == (n-1) ? '\n' : ' ');} // if(cnt == 1 && ans[1] <= x) { // ll all = a[ans[1]];//先存下來(lái) // a[ans[1]]=0; // ll up = all / n;//ans[1] == n-1 ? // all = all-up;//還剩多少需要發(fā)出去 // for(int i = 0; i<n; i++) { // if(i != ans[1]) a[i] += up; // } // for(int i = 1; i<=all; i++) { // a[(ans[1]+i)%n]++; // } // }return 0 ;}

總結(jié)：

? 其實(shí)這題還可以：

? ? ? ? ?首先不難證明出必須要選擇最小的，，，（一開(kāi)始以為還有可能是第二小的，后來(lái)發(fā)現(xiàn)題意理解錯(cuò)了，，我出發(fā)點(diǎn)的值要變成1，一定是發(fā)了完整一圈以后的結(jié)果，所以和圖形(笛卡爾坐標(biāo)系?或者一個(gè)柱形圖)結(jié)合一下就顯然可證。）然后看在讀入的x左方有沒(méi)有這個(gè)最小值，如果有的話，就用最小值的當(dāng)起點(diǎn)，如果多個(gè)，就用最右端的；如果左方?jīng)]有，那就看右方，如果有的話那就用，如果有多個(gè)，那就用最右端的、、、應(yīng)該這段口胡的算法沒(méi)錯(cuò)、、、抽空嘗試實(shí)現(xiàn)一下。（也就是先看左邊，如果有就找離x最近的；否則看 右邊，此時(shí)一定有，因?yàn)橐ＷC有解，我們看離x最遠(yuǎn)的）

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 260C】Balls and Boxes （思维模拟，有坑，时光倒流）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。