題干：

You are given an array consisting of?nn?integers?a1,a2,…,ana1,a2,…,an, and a positive integer?mm. It is guaranteed that?mm?is a divisor of?nn.

In a single move, you can choose any position?ii?between?11?and?nn?and increase?aiai?by?11.

Let's calculate?crcr?(0≤r≤m?1)0≤r≤m?1)?— the number of elements having remainder?rr?when divided by?mm. In other words, for each remainder, let's find the number of corresponding elements in?aa?with that remainder.

Your task is to change the array in such a way that?c0=c1=?=cm?1=nmc0=c1=?=cm?1=nm.

Find the minimum number of moves to satisfy the above requirement.

Input

The first line of input contains two integers?nn?and?mm?(1≤n≤2?105,1≤m≤n1≤n≤2?105,1≤m≤n). It is guaranteed that?mm?is a divisor of?nn.

The second line of input contains?nn?integers?a1,a2,…,ana1,a2,…,an?(0≤ai≤1090≤ai≤109), the elements of the array.

Output

In the first line, print a single integer — the minimum number of moves required to satisfy the following condition: for each remainder from?00?to?m?1m?1, the number of elements of the array having this remainder equals?nmnm.

In the second line, print?any?array satisfying the condition and can be obtained from the given array?with the minimum number of moves. The values of the elements of the resulting array must not exceed?10181018.

Examples

Input

6 3 3 2 0 6 10 12

Output

3 3 2 0 7 10 14

Input

4 2 0 1 2 3

Output

0 0 1 2 3

題目大意：

給定n和m（保證m是n的因子），給出n個(gè)數(shù)的序列，定義一次操作：任選序列中的一個(gè)位置，使這個(gè)位置上的數(shù)加一。定義c[x]代表a[i]%m==x的數(shù)的個(gè)數(shù)

問(wèn)你最少需要多少次操作，可以使得c[0]=c[1]=c[2]=...=c[m-1]=n/m。

(n<=2e5，a[i]<=1e18)

解題報(bào)告：

剛開(kāi)始想了一個(gè)比較麻煩的做法：首先對(duì)所有數(shù)都%m，因?yàn)槌俗詈筝敵龅男枰?#xff0c;其他時(shí)候a[i]再大都沒(méi)啥作用。然后用兩個(gè)map分別維護(hù)哪些數(shù)的個(gè)數(shù)不夠，哪些數(shù)的個(gè)數(shù)多了，然后貪心的搞。但是這樣有個(gè)問(wèn)題，不方便記錄它對(duì)應(yīng)的是哪些數(shù)。也就意味著不方便輸出原序列。如果題目只要求輸出最少次數(shù)的話，就可以這樣做了。

題解是這樣做的：思想還是把插入的問(wèn)題轉(zhuǎn)化成刪除的問(wèn)題。先把所有余數(shù)都加到一個(gè)set中，然后每讀入一個(gè)數(shù)a[i]，都從set中找距離他最近的數(shù)，并且讓他變到這個(gè)數(shù)。如果x這個(gè)數(shù)已經(jīng)夠了n/m次了，那就從set中刪除。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; set<ll> ss; ll a[MAX],b[MAX],cnt[MAX],n,m,ci,ans; int main() {cin>>n>>m;ci=n/m;for(int i = 0; i<m; i++) ss.insert(i); for(int i = 1; i<=n; i++) scanf("%lld",a+i),b[i] = a[i]%m;for(int tmp,i = 1; i<=n; i++) {if(b[i] > *ss.rbegin()) tmp = *ss.begin();else tmp = *ss.lower_bound(b[i]);cnt[tmp]++;if(cnt[tmp] == ci) ss.erase(tmp);ans += (m+tmp-b[i])%m;a[i] += (m+tmp-b[i])%m;}printf("%lld\n",ans);for(int i = 1; i<=n; i++) printf("%lld ",a[i]);return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 999D】Equalize the Remainders（思维，贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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