You are given an array consisting of $n$ integers $a_1, a_2, \dots, 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 \le r \le 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 = \dots = c_{m-1} = \frac{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 \le n \le 2 \cdot 10^5, 1 \le m \le n$). It is guaranteed that $m$ is a divisor of $n$.

The second line of input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 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 $\frac{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

Difficulty: introductory

Starter code:

Solutions:
import bisect

n, m = map(int, input().split())
ls = list(map(int, input().split()))

mls = []
for i in range(0, n):
    mls.append((ls[i] % m, i))

mls.sort()
# print(mls)

bk1 = set()
bk2 = set()

aim = n // m
cnt = 0

mis = []
for i in range(m):
    for j in range(aim):
        mis.append(i)

p1 = 0
p2 = 0

while p2 < n:
    if mls[p1][0] > mis[p2]:
        p2 += 1
    else:
        a = mis[p2] - mls[p1][0]
        ls[mls[p1][1]] += a
        cnt += a
        bk2.add(p2)
        p1 += 1
        p2 += 1

if p1 < n and p2 == n:
    p1 = n
    for i in range(p2):
        if i not in bk2:
            p1 -= 1
            a = m - mls[p1][0] + mis[i]
            ls[mls[p1][1]] += a
            cnt += a

print(cnt)
for i in ls:
    print(i, end=' ')



n, m = map(int,input().split())
a = list(map(int,input().split()))
f = [[] for i in range(m)]
l = [0 for i in range(m)]
for i in range(n):
    f[a[i] % m].append(i)
    l[a[i] % m] += 1
k = n // m
j = 0
tot = 0
for i in range(m):
    while l[i] > k:
        while l[j] >= k:
            j = (j + 1) % m
        tot += (j + m - i) % m
        l[j] += 1
        a[f[i][-1]] += (j + m - i) % m
        f[i].pop()
        l[i] -= 1
    if i == j:
        j += 1
print(tot)
for i in a:
    print(i,end=' ')


n,m = list(map(int, input().split()))
assert n % m == 0
k = n // m
a = [*list(map(int, input().split()))]
inds = [[] for r in range(m)]
for i,v in enumerate(a):
  inds[v%m].append(i)
extras = []
for r in range(2*m):
  r %= m
  if len(inds[r]) == k: continue
  elif len(inds[r]) > k:
    extras.extend(inds[r][k:])
    inds[r] = inds[r][:k]
  elif len(inds[r]) < k:
    for _ in range(min(k-len(inds[r]), len(extras))):
      inds[r].append(extras.pop())
  else: assert False
res = 0
for r in range(m):
  for i in inds[r]:
    if a[i] % m > r:
      res += m - (a[i] % m)
      a[i] += m - (a[i] % m)
    res += (r - a[i] % m)
    a[i] += (r - a[i] % m)
print(res)
print(' '.join(map(str, a)))


k=int(input().split()[1])
l=list()
sc=[0]*k
for i in input().split():
    l.append(int(i))
goal=len(l)/k
cpt=0
s=""
dict={}
for i in range(len(l)):
    ok=0
    init=l[i]%k
    ltc=list()
    while(not ok):
        div=l[i]%k
        if(sc[div]<goal):
            sc[div]+=1
            ok=1
            for j in ltc:
                dict[j]=div
        else:
            ltc.append(div)
            #chercher dans la map si on a déjà été ici
            if(div in dict.keys()):
                nd=dict[div]
                diff=(nd-div)%k
                cpt+=diff
                l[i]+=diff
            else:
                cpt+=1
                l[i]+=1
    s+=str(l[i])+" "
print(cpt)
print(s[:len(s)-1])

3


from queue import Queue
import sys
import math
import os.path


def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


# INPUT
def ni():
    return list(map(int, input().split()))


def nio(offset):
    return [int(x) + offset for x in input().split()]


def nia():
    return list(map(int, input().split()))

# CONVERT


def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def toMapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}


# MAIN

n,m = ni()
a = nia()

nm = n // m

mmap = [[] for _ in range(m)]

for i in range(n) :
    xx = a[i] % m
    mmap[xx].append(i)

# log(n,m)
# log(mmap)

move = []
destination = []

for i in range(m):
    ddu = mmap[i]
    x = len(ddu)
    destination.extend([i]*(nm-x))
    move.extend(ddu[nm:x])
    
# log("move",move)
# log("dest",destination)

ssum = 0
lenmove = len(move)
sMoveId = sorted(list(range(lenmove)), key=lambda k: a[move[k]] % m)

# log("smId",sMoveId)
di = 0
for i in range(lenmove):
    moveId = sMoveId[i]
    s = a[move[moveId]] % m    
    while destination[di] < s:
        destination.append(destination[di]+m)
        di += 1    
    d = destination[di]
    di += 1
    ssum += d-s

    # log("move ", move[moveId],"as",a[move[moveId]],s," to ", d, ssum)
    a[move[moveId]] += d-s

print(ssum)
print(toString(a))
    


import sys
from collections import Counter

def i_ints():
    return list(map(int, sys.stdin.readline().split()))

n, m = i_ints()
a = list(i_ints())

r = [x % m for x in a]
c = Counter(r)
c = [c[i] for i in range(m)]

rem2ind = [[] for i in range(m)]
for i, x in enumerate(r):
    rem2ind[x].append(i)
    

R = n // m

for i, inds in enumerate(rem2ind):
    if len(inds) > R:
        next_big = i
        break
else:
    next_big = m
next_small = next_big + 1
#for i in range(next_big + 1, next_big + m):
#    if len(rem2ind[i%m]) < R:
#        next_small = i
#        break

moves = 0
while next_big < m:
    next_small = max(next_small, next_big + 1)
    num = max(c[next_big] - R, 0)
    while num > 0:
        num2 = max(R - c[next_small%m], 0)
        delta = min(num, num2)
        num -= delta
        c[next_small%m] += delta
        step = next_small - next_big
        for i in rem2ind[next_big][num:num+delta]:
            a[i] += step
        moves += delta * step
        if c[next_small%m] >= R:
            next_small += 1
#        print(next_big, next_small, delta, step, moves)
    next_big += 1
            
print(moves)
print( " ".join(map(str, a)))



#def distribute(k, i):
#    """ distribute i elements from position k to the following positions, not exceeding R"""
#    while i > 0:
#        c[k] -= i
#        moves[k] += i
#        k = (k+1) % m
#        c[k] += i
#        i = max(0, c[k] - R)
#    
#moves = [0] * m
#    
#for k in range(m):
#    if c[k] > R:
#        distribute(k, c[k] - R)
#        
#print(sum(moves))
#
#for k, x in enumerate(a):
#    while moves[x%m]:
#        moves[x%m] -= 1
#        x += 1
#    a[k] = x
#
#print( " ".join(map(str, a)))


n,m = list(map(int, input().split()))
nums = list(map(int, input().split()))

# 0 to m-1 remainders
remainder = [0]*m
limit = n//m
moves = 0

for i in nums:
    remainder[i%m] += 1

for i in range(m):
    remainder[i] -= limit

deficit = set() 
for i in range(m):
    if remainder[i] < 0:
        deficit.add(i)

#print(remainder)
#print(deficit)
spare = []
convert = {}

i = 0
while len(deficit) > 0:
    i = i%m

    if remainder[i] > 0:
        spare.append([i, remainder[i]])
        remainder[i] = 0
    elif remainder[i] < 0:
        if len(spare) > 0:
            while len(spare) > 0 and remainder[i] < 0:
                rem = min(spare[-1][1],abs(remainder[i]))

                if spare[-1][0] in list(convert.keys()):
                    convert[spare[-1][0]].append([(i - spare[-1][0])%m, rem]) 
                else:
                    convert[spare[-1][0]] = [[(i - spare[-1][0])%m,rem]]

                spare[-1][1] -= rem
                remainder[i] += rem

                if spare[-1][1] == 0:
                    spare.pop()
            
            if remainder[i] == 0:
                deficit.remove(i)
    
    i += 1

for i in range(n):
    rem = nums[i]%m

    if rem in list(convert.keys()):
        moves += convert[rem][-1][0]
        nums[i] += convert[rem][-1][0]
        convert[rem][-1][1] -= 1

        if convert[rem][-1][1] == 0:
            convert[rem].pop()
        
        if len(convert[rem]) == 0:
            del convert[rem]
#print(convert)
print(moves)
print(*nums)


n,m = list(map(int, input().split()))
nums = list(map(int, input().split()))

# 0 to m-1 remainders
remainder = [0]*m
limit = n//m
moves = 0

for i in nums:
    remainder[i%m] += 1

for i in range(m):
    remainder[i] -= limit

deficit = set() 
for i in range(m):
    if remainder[i] < 0:
        deficit.add(i)

#print(remainder)
#print(deficit)
spare = []
convert = {}

i = 0
while len(deficit) > 0:
    i = i%m

    if remainder[i] > 0:
        spare.append([i, remainder[i]])
        remainder[i] = 0
    elif remainder[i] < 0:
        if len(spare) > 0:
            while len(spare) > 0 and remainder[i] < 0:
                rem = min(spare[-1][1],abs(remainder[i]))

                if spare[-1][0] in list(convert.keys()):
                    convert[spare[-1][0]].append([(i - spare[-1][0])%m, rem]) 
                else:
                    convert[spare[-1][0]] = [[(i - spare[-1][0])%m,rem]]

                spare[-1][1] -= rem
                remainder[i] += rem

                if spare[-1][1] == 0:
                    spare.pop()
            
            if remainder[i] == 0:
                deficit.remove(i)
    
    i += 1

for i in range(n):
    rem = nums[i]%m

    if rem in list(convert.keys()):
        moves += convert[rem][-1][0]
        nums[i] += convert[rem][-1][0]
        convert[rem][-1][1] -= 1

        if convert[rem][-1][1] == 0:
            convert[rem].pop()
        
        if len(convert[rem]) == 0:
            del convert[rem]
#print(convert)
print(moves)
print(*nums)


n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
s = sum(a)
x = [[] for i in range(m)]
for i in range(n): x[a[i] % m].append(i)
j = 0
for i in range(m):
    while len(x[i]) > n // m:
        while j < i or len(x[j % m]) >= n // m: j += 1
        k = x[i].pop()
        a[k] += (j - i) % m
        x[j % m].append(k)
print(sum(a) - s)
print(*a)


n,m=map(int,input().split())
a=list(map(int,input().split()))
d={}
for i in range(m):
	d[i]=[]
for i in range(len(a)):
	r=a[i]%m
	d[r].append((a[i],i))
# print(d)
step=0
x=n//m
stack=[]
# print(d)
for i in range(2*m):
	i=i%m
	# print(i,stack)
	while(len(d[i])>x):
		stack.append(d[i].pop())
	while(len(d[i])<x and len(stack)):
		z=list(stack.pop())
		delta=(i+m-(z[0]%m))%m
		z[0]+=delta
		d[i].append((z[0],z[1]))
		step+=delta
arr=[]
# print(d)
for i in d:
	for j in d[i]:
		arr.append(j)
arr.sort(key=lambda i: i[1])
print(step)
for i in arr:
	print(i[0],end=" ")
print()

import collections

n, m = map(int, input().split())
a = list(map(int, input().split()))
md = n // m
c = [[] for _ in range(m)]
mx, ind, moves = (0,) * 3
movable = collections.deque()
change = []

for i in range(n):
    c[a[i] % m].append(i)

for i in range(m):
    req = md - len(c[i])
    if req <= 0:
        for j in range(-req):
            movable.append(i)
    else:
        while req > 0:
            if len(movable) == 0:
                change.append([i, req])
                break
            old = movable[0]
            add = i - old
            a[c[old][-1]] += add
            moves += add

            c[i].append(c[old][-1])
            del c[old][-1]
            movable.popleft()
            req -= 1

for obj in change:
    i, req = obj[0], obj[1]
    while req > 0:
        old = movable[0]
        add = i + m - old
        a[c[old][-1]] += add
        moves += add

        c[i].append(c[old][-1])
        del c[old][-1]
        movable.popleft()
        req -= 1

# print(c)
ans = [0 for _ in range(n)]

for i in range(m):
    for j in range(md):
        ans[c[i][j]] = a[c[i][j]]

print(moves)
print(*ans)

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
s = sum(a)
x = [[] for i in range(m)]
for i in range(n): 
    x[a[i] % m].append(i)
j = 0
for i in range(m):
    while len(x[i]) > n // m:
        while j < i or len(x[j % m]) >= n // m: 
            j += 1
        k = x[i].pop()
        a[k] += (j - i) % m
        x[j % m].append(k)
print(sum(a) - s)
print(*a)


import collections

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
d = collections.defaultdict(set)
kr = [-n//k] * k

for i in range(n):
  ri = a[i] % k
  kr[ri] += 1
  d[ri].add(i)

krs = [0] * k
krs[0] = kr[0]
for i in range(1, k):
  krs[i] = krs[i-1] + kr[i]

org = (krs.index(min(krs))+1)%k
cnt = sum(abs(i) for i in kr) // 2
aa = [0] * cnt
bb = [0] * cnt
ai = bi = 0

for ii in range(org, org+k):
  i = ii % k
  if kr[i] > 0:
    for _ in range(kr[i]):
      aa[ai] = i
      ai += 1
  elif kr[i] < 0:
    for _ in range(-kr[i]):
      bb[bi] = i
      bi += 1

ans = 0
for ai, bi in zip(aa,bb):
  diff = (bi-org)%k - (ai-org)%k
  ans += diff
  i = d[ai].pop()
  a[i] += diff

print(ans)
print(' '.join(map(str, a)))


n, m = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
x = [[] for i in range(m)]
for i in range(n): x[a[i] % m].append(i)
j = 0
for i in range(m):
    while len(x[i]) > n // m:
        while j < i or len(x[j % m]) >= n // m: j += 1
        k = x[i].pop()
        a[k] += (j - i) % m
        x[j % m].append(k)
print(sum(a) - s)
print(*a)

from collections import defaultdict

n,m = map(int,input().split())
k = n//m
l = list(map(int,input().split()))
s = sum(l)
#mod_list = []
occ = defaultdict(list)
for i,a in enumerate(l):
    rem = a%m
    occ[rem].append(i)
    #mod_list.append(rem)

j = 0
for i in range(m):
    while len(occ[i]) > k:
        while j < i or len(occ[j % m]) >= k: j += 1
        key = occ[i].pop()
        l[key] += (j - i) % m
        occ[j % m].append(k)
print(sum(l) - s)
print(*l)

n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
res, cnt = sum(aa), [-n // m] * m
acc = [[] for _ in range(m)]
for i, a in enumerate(aa):
    r = a % m
    cnt[r] += 1
    acc[r].append(i)
icnt, a = [], 0
for c in cnt:
    a += c
    icnt.append(a)
start = (min(range(m), key=icnt.__getitem__) + 1) % m
excess, scarce = [], []
for r in range(start, m), range(start):
    for i in r:
        if cnt[i] > 0:
            for _ in range(cnt[i]):
                excess.append(i)
        elif cnt[i] < 0:
            for _ in range(-cnt[i]):
                scarce.append(i)
for e, s in zip(excess, scarce):
    aa[acc[e].pop()] += (s - e) % m
print(sum(aa) - res)
print(' '.join(map(str, aa)))

n, m = map(int, input().split())
aa = list(map(int, input().split()))
res, q = sum(aa), n // m
acc = [[] for _ in range(m)]
for i in range(n):
    acc[aa[i] % m].append(i)
j = -m
for i, l in enumerate(acc):
    if len(l) > q:
        if j <= i - m:
            j = i - m + 1
        while len(l) > q:
            while len(acc[j]) >= q:
                j += 1
            aa[l.pop()] += j + m - i
            acc[j].append(0)
print(sum(aa) - res)
print(' '.join(map(str, aa)))

from collections import deque

n, m = map(int, input().split())
a = list(map(int, input().split()))

n_m = n // m
c = m * [0]
indices = [deque() for r in range(m)]

for i, ai in enumerate(a):
    r = ai % m
    c[r] += 1
    indices[r].append(i)

n_moves = 0
queue = deque()

for i in range(0, 2 * m):
    r = i % m
    
    while c[r] > n_m:
        queue.append((i, indices[r].pop()))
        c[r] -= 1
    
    while c[r] < n_m and queue:
        j, index = queue.popleft()
        indices[r].append(index)
        c[r] += 1
        a[index] += i - j
        n_moves += i - j

print(n_moves)
print(*a)

n,m = map(int,input().split())
a = list(map(int,input().split()))
k = int(n/m)
lis = [ [] for i in range(m+1)]

free = list()

for i in range(n):
    ele = a[i]%m
    lis[ele].append(i)

ans = 0

for i in range(2*m):
    cur = i%m
    
    while len(lis[cur])>k:
        ele = lis[cur].pop()
        free.append([ele,i])
    
    while len(lis[cur])<k and free!=[]:
        ele,mm = free.pop()
        #print(ele,mm)
        lis[cur].append(ele)
        a[ele]+=(i-mm)
        ans+=(i-mm)
print(ans)
for item in a:
    print(item,end=" ")

        
        
        

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
s = [[] for _ in range(m)]

for i in range(n):
    s[a[i] % m].append(i)

f = []
c = 0

for _ in range(2):
    for i in range(m):
        while len(s[i]) > n // m:
            f.append((s[i].pop(), i))
        while len(s[i]) < n // m and f:
            v, p = f.pop()
            s[i].append(v)
            if i > p:
                d = i - p
            else:
                d = i + m - p
            a[v] += d
            c += d

print(c)
print(*a)


import sys
input = sys.stdin.readline
out = sys.stdout

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    query = n//m
    data = {i: 0 for i in range(n)}
    data_stat = {i: set() for i in range(m)}
    for i in range(n):
        data[i] = a[i]
        data_stat[a[i] % m].add(i)
    free = []
    answer = {i: 0 for i in range(n)}
    result = 0
    for i in range(2*m):
        cur = i % m
        while len(data_stat[cur]) > query:
            elem = data_stat[cur].pop()
            free.append((elem, i))
        while len(data_stat[cur]) < query and free != []:
            elem, mmod = free.pop()
            data_stat[cur].add(elem)
            a[elem] += i - mmod
            result += i - mmod        
    print(result)
    for j in a:
        out.write(str(j) + ' ')

def __starting_point():
    main()
__starting_point()

import collections
n,m = [int(x) for x in input().split()]

L = [int(x) for x in input().split()]

J = [0]*m
D = []
for i in range(m):
    D.append([])
x = n//m
s = 0
for i in range(m):
    D[i] = []
for i in range(n):
    J[L[i]%m] += 1
    D[L[i]%m].append(i)

Free = collections.deque([])
F = 0
for i in range(2*m-1):
    j = i%m
    if J[j] > x:
        t = J[j] - x
        F += t
        for A in range(t):
            Free.append((j,D[j][A]))
        J[j] = x
    elif J[j] < x:
        while (F > 0) and (J[j] < x):
            F -= 1
            J[j] += 1
            a,b = Free.popleft()
            s += (j-a)%m
            L[b] += (j-a)%m
print(s)
for i in L:
    print(i, end = ' ')

n, m = map(int, input().split())
a = list(map(int, input().split()))
k, c, free = n // m, [[] for _ in range(m)], []
for i, ai in enumerate(a):
	c[ai % m].append(i)
ans = 0
for _ in range(2 * m):
	i = _ % m
	lci = len(c[i])
	for j in range(k, lci)[::-1]:
		free.append((c[i][j], i))
		c[i].pop()
	for j in range(k - lci):
		if free:
			to_add = (i - free[-1][1]) % m
			ans += to_add
			a[free[-1][0]] += to_add
			c[i].append(free[-1][0])
			free.pop()
print(ans)
print(*a)