You are given an array consisting of n integers a_1, a_2, ..., a_n, and a positive integer m. It is guaranteed that m is a divisor of n.

In a single move, you can choose any position i between 1 and n and increase a_i by 1.

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

Your task is to change the array in such a way that c_0 = c_1 = ... = c_{m-1} = n/m.

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

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m ≤ n). It is guaranteed that m is a divisor of n.

The second line of input contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9), 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 0 to m - 1, the number of elements of the array having this remainder equals n/m.

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 10^{18}.

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 
	// Code Author: Shrey Shah
	 
	import java.io.*;
	import java.math.BigInteger;
	import java.math.RoundingMode;
	import java.text.DecimalFormat;
	import java.util.*;
	
	
	public class Tester3 {
	
		static double eps=(double)1e-6;
		static long mod=1000000007;
		 static long d,x ,y;
		public static void main(String args[]){
			InputReader sc = new InputReader(System.in);
			OutputStream outputStream = System.out;
			PrintWriter out = new PrintWriter(outputStream);
			//----------My Code----------
				int n = sc.nextInt();
				int m = sc.nextInt();
				int k = n/m;
				int a[] = new int[n];
				ArrayList<Integer> rem[] = new ArrayList[m];
				for(int i=0;i<m;i++)
					rem[i] = new ArrayList<Integer>();
				for(int i=0;i<n;i++)
				{
					a[i] = sc.nextInt();
					int ind = a[i]%m;
					rem[ind].add(i);
				}
				long ans=0;
				ArrayList<Pair> extra = new ArrayList<Pair>();
				for(int i=0;i<2*m;i++)
				{
					int current = i%m;
					while(rem[current].size()>k)
					{
						int value = rem[current].remove(rem[current].size()-1);
						extra.add(new Pair(value,i));
					}
					while(rem[current].size()<k && !extra.isEmpty())
					{
						int value = extra.get(extra.size()-1).x;
						int mod = extra.get(extra.size()-1).y;
						extra.remove(extra.size()-1);
						
						rem[current].add(value);
						a[value]+= i-mod;
						ans+=i-mod;
					}
				}
				out.println(ans);
				for(int i=0;i<n;i++)
					out.print(a[i]+" ");
				//----------The End----------
			out.close();
		}
		public static void reverseArray(char arr[], int start, int end)
		{
		    while (start < end)
		    {
		        char temp = arr[start]; 
		        arr[start] = arr[end];
		        arr[end] = temp;
		        start++;
		        end--;
		    } 
		}
		static String reverse(String s)
		{
			String ans="";
			for(int i=s.length()-1;i>=0;i--)
				ans+=s.charAt(i);
			return ans;
		}
		static long nearestPrime(long x)
		{
			long left=x-1;
			long right=x+1;
			
			long count=400;
			while(count>0)
			{
				if(isPrime(left))
					break;
				
				left--;
				count--;
			}
			count=301;
			while(count>0)
			{
				if(isPrime(right))
					break;
				
				right++;
				count--;
			}
			if(Math.abs(left-x) > Math.abs(right-x))
				return right;
			else if(Math.abs(left-x)<Math.abs(right-x))
				return left;
			else
				return left;
		}
		static boolean isPrime(long n)
		{
			if(n==1 || n==2)
				return true;
			for(long i=2;i*i<=n;i++)
				if(n%i==0)
					return false;
			return true;
		}
		 static long modInverse(long A, long M)
		    {
		        extendedEuclid(A,M);
		        return (x%M+M)%M;    //x may be negative
		    }
		    static void extendedEuclid(long A, long B) {
		       
		        if(B == 0) {
		            d = A;
		            x = 1;
		            y = 0;
		        }
		        else {
		            extendedEuclid(B, A%B);
		            long temp = x;
		            x = y;
		            y = temp - (A/B)*y;
		        }
		    }
		public static int floor(int arr[], int low, int high, long x)
		{
			for(int i=low;i<high-1;i++)
				if(arr[i]<x && (arr[i+1]>=x))
					return arr[i];
			
			return arr[0];
		}
		
		public static int ceil(int arr[], int low, int high, long x)
		{
			for(int i=low+1;i<high;i++)
			{
				if(arr[i-1]<=x && arr[i]>x)
					return arr[i];
			}
			return arr[high-1];
		}
		public static long[] totient(int n)
		{
		 long phi[] = new long[n + 1];
		    for (long i = 1; i <= n; i++)
		    phi[(int)i] = i; // indicates not evaluated yet
		                // and initializes for product
		                // formula.
		 
		    // Compute other Phi values
		    for (long p = 2; p <= n; p++) 
		    {
		         
			    // If phi[p] is not computed already,
			    // then number p is prime
			    if (phi[(int)p] == p) 
			    {
			         
			        // Phi of a prime number p is
			        // always equal to p-1.
			        phi[(int)p] = p - 1;
			 
			        // Update phi values of all
			        // multiples of p
			        for (long i = 2 * p; i <= n; i += p) 
			        {
			             
			        // Add contribution of p to its
			        // multiple i by multiplying with
			        // (1 - 1/p)
			        	
			        phi[(int)i] = (phi[(int)i]* p) *(p - 1);
			        }
			   }
		   }
		    return phi;
		}
		 private static int max(int a, int b) {
			// TODO Auto-generated method stub
			 
			return (a>b)? a:b;
		}

		static int power(int x,int n)
			{
			    if(n==0)
			        return 1;
			    else if(n%2 == 0)        //n is even
			        return power(x*x,n/2);
			    else                             //n is odd
			        return x*power(x*x,(n-1)/2);
			}
	
		static long ce(long x)
		{
			if(x%2!=0)
				return x/2+1;
			return x/2;
		}
		static boolean isSubSequence(String str1, String str2, int m, int n)
		{
		   int j = 0;
		   for (int i=0; i<n&&j<m; i++)
		       if (str1.charAt(j) == str2.charAt(i))
		         j++;
		 
		   return (j==m);
		}
			
		static long fibo(long l) {
	        if (l < 0) {
	            throw new IllegalArgumentException("The fibo value cannot be negative");
	        }
	
	        if (l <= 1) return l;
	
	        long[][] result = {{1, 0}, {0, 1}}; // identity matrix.
	        long[][] fiboM = {{1, 1}, {1, 0}};
	
	        while (l > 0) {
	            if (l%2 == 1) {
	                multMatrix(result, fiboM);
	            }
	            l = l / 2;
	            multMatrix(fiboM, fiboM);
	        }
	
	        return result[1][0];
	    }
	
	    private static void multMatrix(long[][] result, long[][] fiboM) {
	        long a = (result[0][0]%mod * fiboM[0][0]%mod)%mod +  (result[0][1]%mod * fiboM[1][0]%mod)%mod;
	        long b = (result[0][0]%mod * fiboM[0][1]%mod)%mod + ( result[0][1]%mod * fiboM[1][1]%mod)%mod;
	        long c = (result[1][0]%mod * fiboM[0][0]%mod)%mod + ( result[1][1]%mod * fiboM[0][1]%mod)%mod;
	        long d = (result[1][0]%mod * fiboM[0][1]%mod)%mod +  (result[1][1]%mod * fiboM[1][1]%mod)%mod;
	
	        result[0][0] = a;
	        result[0][1] = b;
	        result[1][0] = c;
	        result[1][1] = d;
	    }
	    
	    
		static int[] sieve(int n)
		{
			int[] arr = new int[n+1];
			for(int i=2;i*i<=n;i++)
			{
				if(arr[i]==0)
				{
					for(int j=i*2;j<=n;j+=i)
						arr[j]=1;
				}
			}
			return arr;
		}
		
		static boolean isPal(String s)
		{
			for(int i=0, j=s.length()-1;i<=j;i++,j--)
			{
				if(s.charAt(i)!=s.charAt(j)) return false;
			}
			return true;
		}
		public static String rev(String s)
		{
			StringBuilder sb=new StringBuilder(s);
			sb.reverse();
			return sb.toString();
		}
		    
		static long lcm(long a, long b)
		{
		    return a * (b / gcd(a, b));
		}
		
		static long gcd(long a, long b)
		{
		    while (b > 0)
		    {
		        long temp = b;
		        b = a % b; // % is remainder
		        a = temp;
		    }
		    return a;
		}
		static long modulo(long a,long b,long c) {
			long x=1;
			long y=a;
			while(b > 0){
				if(b%2 == 1){
					x=(x*y)%c;
				}
				y = (y*y)%c; // squaring the base
				b /= 2;
			}
			return  x%c;
		}
		public static void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
		static class Pair implements Comparable<Pair>{
			int x;
			int y;
			Pair(int xx,int yy){
				x=xx;
				y=yy;
			}
			@Override
			public int compareTo(Pair o) {
				return Integer.compare(this.x, o.x);
			}
		}
	
		static class InputReader {
			public BufferedReader reader;
			public StringTokenizer tokenizer;
	
			public InputReader(InputStream inputstream) {
				reader = new BufferedReader(new InputStreamReader(inputstream));
				tokenizer = null;
			}
	
			public String nextLine(){
				String fullLine=null;
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					try {
						fullLine=reader.readLine();
					} catch (IOException e) {
						throw new RuntimeException(e);
					}
					return fullLine;
				}
				return fullLine;
			}
			public String next() {
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					try {
						tokenizer = new StringTokenizer(reader.readLine());
					} catch (IOException e) {
						throw new RuntimeException(e);
					}
				}
				return tokenizer.nextToken();
			}
			public long nextLong() {
				return Long.parseLong(next());
			}
			public int nextInt() {
				return Integer.parseInt(next());
			}
		}
		
	}
