Polycarp is a music editor at the radio station. He received a playlist for tomorrow, that can be represented as a sequence a_1, a_2, ..., a_{n}, where a_{i} is a band, which performs the i-th song. Polycarp likes bands with the numbers from 1 to m, but he doesn't really like others. 

We define as b_{j} the number of songs the group j is going to perform tomorrow. Polycarp wants to change the playlist in such a way that the minimum among the numbers b_1, b_2, ..., b_{m} will be as large as possible.

Find this maximum possible value of the minimum among the b_{j} (1 ≤ j ≤ m), and the minimum number of changes in the playlist Polycarp needs to make to achieve it. One change in the playlist is a replacement of the performer of the i-th song with any other group.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 2000).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the performer of the i-th song.


-----Output-----

In the first line print two integers: the maximum possible value of the minimum among the b_{j} (1 ≤ j ≤ m), where b_{j} is the number of songs in the changed playlist performed by the j-th band, and the minimum number of changes in the playlist Polycarp needs to make.

In the second line print the changed playlist.

If there are multiple answers, print any of them.


-----Examples-----
Input
4 2
1 2 3 2

Output
2 1
1 2 1 2 




Input
7 3
1 3 2 2 2 2 1

Output
2 1
1 3 3 2 2 2 1 




Input
4 4
1000000000 100 7 1000000000

Output
1 4
1 2 3 4 






-----Note-----

In the first sample, after Polycarp's changes the first band performs two songs (b_1 = 2), and the second band also performs two songs (b_2 = 2). Thus, the minimum of these values equals to 2. It is impossible to achieve a higher minimum value by any changes in the playlist. 

In the second sample, after Polycarp's changes the first band performs two songs (b_1 = 2), the second band performs three songs (b_2 = 3), and the third band also performs two songs (b_3 = 2). Thus, the best minimum value is 2.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from collections import Counter

def main():
	try:
		while True:
			(n, m) = map(int, input().split())
			a = list(map(int, input().split()))
			trg = n // m
			result = 0
			c = Counter(a)
			req = {k: trg - v for (k, v) in c.items()}
			for i in range(1, m + 1):
				if i not in req:
					req[i] = trg
			for (i, x) in enumerate(a):
				if x > m:
					for (y, value) in req.items():
						if y <= m and value > 0:
							a[i] = y
							req[y] = value - 1
							result += 1
							break
				elif req[x] < 0:
					for (y, value) in req.items():
						if y <= m and value > 0:
							a[i] = y
							req[x] += 1
							req[y] = value - 1
							result += 1
							break
			print(trg, result)
			print(*a)
	except EOFError:
		pass
main()


import copy
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
d = copy.copy(a)
a.sort()
s = n // m
b = [0] * m
cnt = 0
q = 0
for el in a:
	if el <= m and b[el - 1] < s:
		b[el - 1] += 1
		q += 1
ans = n - q - n % m
print(s, ans)
a = d
q = copy.copy(b)
pos = 0
for el in a:
	if el <= m and b[el - 1] > 0:
		b[el - 1] -= 1
		print(el, end=' ')
	else:
		while pos < m and q[pos] >= s:
			pos += 1
		if pos < m:
			q[pos] += 1
			print(pos + 1, end=' ')
		else:
			print(el, end=' ')


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
k = n // m
mod = n % m
d = [0] * (m + 1)
R = []
mod1 = 0
for i in range(n):
	if a[i] > m:
		if mod1 < mod:
			mod1 += 1
		else:
			R.append(i)
	elif d[a[i]] == k:
		if mod1 < mod:
			d[a[i]] += 1
			mod1 += 1
		else:
			R.append(i)
	elif d[a[i]] == k + 1:
		R.append(i)
	else:
		d[a[i]] += 1
ans = [-1] * n
for i in range(1, m + 1):
	while d[i] < k:
		j = R.pop(0)
		ans[j] = i
		d[i] += 1
num = 0
for j in range(n):
	if ans[j] == -1:
		ans[j] = a[j]
	else:
		num += 1
print(k, num)
print(*ans)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
d = {k: 0 for k in range(1, M + 1)}
indices = []
ans1 = 0
ans2 = 0
for (i, a) in enumerate(A):
	if a <= M:
		d[a] += 1
	else:
		indices.append(i)
scores = [[k, v] for (k, v) in d.items()]
scores.sort(key=lambda x: x[1])
div = N // M
ind = 0
while scores[0][1] < div:
	if ind == len(indices):
		break
	scores[0][1] += 1
	A[indices[ind]] = scores[0][0]
	ind += 1
	scores.sort(key=lambda x: x[1])
	ans2 += 1
sum_score = sum([s[1] for s in scores])
mean = sum_score // M
while scores[0][1] < mean:
	A[A.index(scores[-1][0])] = scores[0][0]
	scores[0][1] += 1
	scores[-1][1] -= 1
	scores.sort(key=lambda x: x[1])
	ans2 += 1
print('{} {}'.format(scores[0][1], ans2))
print(' '.join(map(str, A)))


(n, m) = map(int, input().split())
A = list(map(int, input().split()))
count_good = [[0, i + 1] for i in range(m)]
bad = 0
bad_places = []
good_places = [[i + 1, []] for i in range(m)]
for i in range(len(A)):
	elem = A[i]
	if elem <= m:
		count_good[elem - 1][0] += 1
		good_places[elem - 1][1].append(i)
	else:
		bad += 1
		bad_places.append(i)
ideal = n // m
for elem in good_places:
	bad_places.extend(elem[1][ideal:])
bad = len(bad_places)
badd = bad
count_good.sort()
minn = count_good[0][0]
bad_Cnt = 0
while minn != ideal:
	j = 0
	while j < len(count_good) and count_good[j][0] == minn and (bad > 0):
		count_good[j][0] += 1
		A[bad_places[bad_Cnt]] = count_good[j][1]
		bad_Cnt += 1
		bad -= 1
		j += 1
	minn += 1
print(minn, badd - bad)
print(*A)


import sys
import bisect
input = sys.stdin.readline

def takeSecond(elem):
	return elem[1]

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = 1
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	b = [0] * n
	for i in range(n):
		d[l[i]] = d.get(l[i], 0) + 1
	suma = 0
	for i in d:
		suma += d[i]
	ans1 = suma // m
	ans2 = 0
	for j in range(n):
		if d[l[j]] < ans1 and l[j] <= m:
			req = ans1 - d[l[j]]
			for i in range(n):
				if l[i] != l[j]:
					if (d[l[i]] > ans1 or l[i] > m) and req > 0:
						d[l[i]] -= 1
						d[l[j]] += 1
						req -= 1
						ans2 += 1
						l[i] = l[j]
	for j in range(1, m + 1):
		if d.get(j, -1) == -1:
			req = ans1
			for i in range(n):
				if (d[l[i]] > ans1 or l[i] > m) and req > 0:
					req -= 1
					ans2 += 1
					d[l[i]] -= 1
					l[i] = j
					d[l[i]] = d.get(l[i], 0) + 1
	print(ans1, ans2)
	print(*l)


from collections import Counter
(n, m) = map(int, input().split())
nums = list(map(int, input().split()))
cnts = dict(Counter(nums))
for i in range(1, m + 1):
	if i not in cnts:
		cnts[i] = 0

def minner():
	return min(cnts.items(), key=lambda x: x[1])
n //= m
res = 0
for (i, num) in enumerate(nums):
	if num > m or cnts[num] > n:
		for r in range(1, m + 1):
			if cnts[r] < n:
				cnts[num] -= 1
				nums[i] = r
				cnts[r] += 1
				res += 1
				break
print(n, res)
print(' '.join(map(str, nums)))


d = input().split()
(n, m) = (int(d[0]), int(d[1]))
d = input().split()
d = [int(x) for x in d]
p = 0
di = {}
for i in range(1, 1 + m):
	di[i] = 0
for i in d:
	if i <= m:
		di[i] += 1
for i in range(1, 1 + m):
	if di[i] < n // m:
		p += abs(di[i] - n // m)
print(n // m, p)
D = []
for i in range(1, m + 1):
	if di[i] < n // m:
		D += [i] * (n // m - di[i])
for i in range(n):
	if D != []:
		if d[i] > m:
			d[i] = D.pop(-1)
		elif di[d[i]] > n // m:
			di[d[i]] -= 1
			d[i] = D.pop(-1)
for i in d:
	print(i, end=' ')


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [a[i] for i in range(n)]
pos = [[] for i in range(m + 1)]
not_use = []
for i in range(n):
	if a[i] > m:
		not_use.append(i)
	else:
		pos[a[i]].append(i)
for i in range(1, m + 1):
	if len(pos[i]) > n // m:
		not_use.extend(pos[i][:len(pos[i]) - n // m])
		pos[i] = pos[i][len(pos[i]) - n // m:]
cnt = 0
for i in range(1, m + 1):
	while len(pos[i]) < n // m and not_use:
		idx = not_use.pop()
		b[idx] = i
		cnt += 1
		pos[i].append(idx)
print(n // m, cnt)
print(*b)


import collections
(n, m) = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]
ctr = collections.Counter(a)
nummin = n // m
inses = []
for b in range(1, m + 1):
	if ctr[b] < nummin:
		inses.extend([b] * (nummin - ctr[b]))
num_ins = 0
for i in range(n):
	b = a[i]
	if ctr[b] > nummin or b > m:
		if num_ins >= len(inses):
			break
		a[i] = inses[num_ins]
		ctr[b] -= 1
		num_ins += 1
print(nummin, len(inses))
print(' '.join(map(str, a)))


(n, m) = map(int, input().split())
n //= m
A = list(map(int, input().split()))
S = [n] * m
L = []
for (i, a) in enumerate(A):
	a -= 1
	if m > a and S[a]:
		S[a] -= 1
	else:
		L.append(i)
for (i, s) in enumerate(S, 1):
	for _ in range(s):
		A[L.pop()] = i
print(n, sum(S))
print(*A)


(n, m) = map(int, input().split())
ans = n // m
A = list(map(int, input().split()))
B = [0 for i in range(m)]
for i in A:
	if i <= m:
		B[i - 1] += 1
ost = n - m * ans
change = 0
for i in range(m):
	if B[i] < ans:
		change += ans - B[i]
print(ans, change)
b = True
ind = 0
for i in A:
	if b and (i > m or B[i - 1] > ans):
		while b and B[ind] >= ans:
			ind += 1
			if ind >= m:
				b = False
				print(i, end=' ')
		if b:
			B[ind] += 1
			if i <= m:
				B[i - 1] -= 1
			print(ind + 1, end=' ')
	else:
		print(i, end=' ')


(n, m) = [int(i) for i in input().split()]
data = [int(i) for i in input().split()]
d = n // m
dct = {}
keys = [i + 1 for i in range(m)]
for i in keys:
	dct[i] = 0
for i in data:
	if i <= m:
		dct[i] += 1
cnt = {}
for i in keys:
	cnt[i] = d - dct[i]
box = []
l = 0
for i in keys:
	for j in range(cnt[i]):
		box.append(i)
		l += 1
ind = 0
print(d, l)
for i in data:
	if ind != l:
		if i <= m and cnt[i] < 0:
			cnt[i] += 1
			print(box[ind], end=' ')
			ind += 1
		elif i > m:
			print(box[ind], end=' ')
			ind += 1
		else:
			print(i, end=' ')
	else:
		print(i, end=' ')


import sys

def solve(n, m, ns):
	count = n // m
	counts = {i: 0 for i in range(1, m + 1)}
	for i in ns:
		if i <= m:
			counts[i] += 1
	countsSmall = []
	for c in counts:
		val = counts[c]
		if val < count:
			countsSmall.append([c, val])
	changes = 0
	for i in range(len(ns)):
		if len(countsSmall) == 0:
			break
		if ns[i] > m or (ns[i] <= m and counts[ns[i]] > count):
			if ns[i] <= m:
				counts[ns[i]] -= 1
			ns[i] = countsSmall[-1][0]
			changes += 1
			if countsSmall[-1][1] == count - 1:
				countsSmall.pop()
			else:
				countsSmall[-1][1] += 1
	print(count, changes)
	print(' '.join([str(i) for i in ns]))
(n, m) = [int(i) for i in sys.stdin.readline().split()]
ns = [int(i) for i in sys.stdin.readline().split()]
solve(n, m, ns)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1
for _ in range(t):
	(n, m) = mapin()
	l = [int(x) for x in input().split()]
	d = []
	for i in range(m + 1):
		d.append([0, []])
	f = []
	for i in range(n):
		if l[i] <= m:
			d[l[i]][0] += 1
			d[l[i]][1].append(i)
		else:
			f.append(i)
	s = n // m
	ss = 0
	mm = 0
	for i in range(1, m + 1):
		if d[i][0] >= s:
			for j in range(d[i][0] - s):
				f.append(d[i][1][j])
	for i in range(1, m + 1):
		if d[i][0] < s:
			for j in range(s - d[i][0]):
				l[f[mm]] = i
				ss += 1
				mm += 1
	print(s, ss)
	print(*l)


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
minB = n // m
b = [0] * (m + 1)
pofig = set()
for i in range(n):
	if a[i] > m:
		pofig.add(i)
	elif b[a[i]] >= minB:
		pofig.add(i)
	else:
		b[a[i]] += 1
i = 0
ans = 0
for k in range(1, m + 1):
	while b[k] < minB:
		while not i in pofig:
			i += 1
		a[i] = k
		b[k] += 1
		ans += 1
		i += 1
print(minB, ans)
for i in a:
	print(i)


from statistics import mode
(n, m) = map(int, input().split())
playlist = list(map(int, input().split()))
divided = n // m
occurences = dict()
for i in range(1, m + 1):
	occurences[i] = 0
for p in playlist:
	if p <= m:
		occurences[p] += 1
lack = []
lackquantity = []
for i in range(1, m + 1):
	if occurences[i] < divided:
		lack.append(i)
		lackquantity.append(divided - occurences[i])
out = dict()
output = []
changes = 0
for i in range(1, m + 1):
	out[i] = 0
for p in playlist:
	if p <= m:
		if out[p] < divided:
			output.append(str(p))
			out[p] += 1
			continue
		elif len(lack) > 0:
			output.append(str(lack[0]))
			out[lack[0]] += 1
			changes += 1
			lackquantity[0] -= 1
			if lackquantity[0] == 0:
				lack.pop(0)
				lackquantity.pop(0)
			continue
		else:
			output.append(str(p))
			out[p] += 1
			continue
	elif len(lack) > 0:
		output.append(str(lack[0]))
		out[lack[0]] += 1
		changes += 1
		lackquantity[0] -= 1
		if lackquantity[0] == 0:
			lack.pop(0)
			lackquantity.pop(0)
		continue
	else:
		output.append(str(p))
		continue
print(str(divided) + ' ' + str(changes))
print(' '.join(output))


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
n //= m
bands = [n] * (m + 1)
bands2 = []
for (i, a) in enumerate(arr):
	if a <= m and bands[a]:
		bands[a] -= 1
	else:
		bands2.append(i)
for (i, s) in enumerate(bands[1:], 1):
	for _ in range(s):
		arr[bands2.pop(0)] = i
print(n, sum(bands[1:]))
print(*arr)


(n, m) = list(map(int, input().split()))
count = [0] * (m + 1)
lother = []
lbig = []
a = list(map(int, input().split()))
for i in range(len(a)):
	if a[i] <= m:
		count[a[i]] += 1
	else:
		lother.append(i)
for i in range(len(a)):
	if a[i] <= m and count[a[i]] > n // m:
		lbig.append(i)
		count[a[i]] -= 1
ans = 0
for i in range(1, m + 1):
	while count[i] < n // m:
		ans += 1
		if len(lother) != 0:
			a[lother[0]] = i
			lother.pop(0)
		else:
			a[lbig[0]] = i
			lbig.pop(0)
		count[i] += 1
print(str(n // m) + ' ' + str(ans))
for i in a:
	print(i, end=' ')


from collections import defaultdict
import sys, os, math
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
cnt = [0] * 2100
(t, d) = (n // m, n % m)
chan = 0
for i in range(n):
	if arr[i] <= m:
		cnt[arr[i]] += 1
for i in range(n):
	if arr[i] <= m:
		if cnt[arr[i]] <= t:
			pass
		elif d > 0:
			d -= 1
		else:
			for j in range(1, m + 1):
				if cnt[j] < t:
					cnt[j] += 1
					cnt[arr[i]] -= 1
					arr[i] = j
					chan += 1
					break
	else:
		for j in range(1, m + 1):
			if cnt[j] < t:
				cnt[j] += 1
				arr[i] = j
				chan += 1
				f = False
				break
		continue
print(t, chan)
print(' '.join((str(s) for s in arr)))


(n, m) = map(int, input().split())
target = n // m
A = [int(i) for i in input().split()]
B = [0 for _ in range(2005)]
R = B[:]
ch = 0
for i in A:
	if i <= m:
		B[i] += 1
for i in range(2005):
	R[i] = target - B[i]
j = 1
for i in range(n):
	if A[i] > m:
		while j <= m and R[j] <= 0:
			j += 1
		if j <= m and R[j] > 0:
			ch += 1
			R[j] -= 1
			A[i] = j
for i in range(n):
	if A[i] <= m and R[A[i]] < 0:
		while j <= m and R[j] <= 0:
			j += 1
		if j <= m and R[j] > 0:
			R[j] -= 1
			R[A[i]] += 1
			A[i] = j
			ch += 1
print(target, ch)
print(*A)


(n, m) = (int(x) for x in input().split())
l = [int(x) for x in input().split()]
count = [0] * (m + 1)
overcount = 0
dielist = []
changelist = []
maxmin = int(n / m)
for (ind, i) in enumerate(l):
	if i <= m:
		count[i] += 1
		if count[i] > maxmin:
			dielist.append(ind)
	else:
		dielist.append(ind)
changes = 0
for i in range(1, len(count)):
	c = count[i]
	if c < maxmin:
		changes += maxmin - c
		for j in range(maxmin - c):
			l[dielist[overcount]] = i
			overcount += 1
print(maxmin, changes)
print(' '.join([str(x) for x in l]))


from collections import deque
(n, m) = map(int, input().split())
k = n // m
a = list(map(int, input().split()))
l = deque([])
cnt = [0] * (1 + m)
for i in range(n):
	if a[i] > m:
		l.append(i)
	else:
		if cnt[a[i]] >= k:
			l.append(i)
		cnt[a[i]] += 1
chg = 0
for i in range(1, m + 1):
	if cnt[i] < k:
		for _ in range(k - cnt[i]):
			idx = l.popleft()
			a[idx] = i
			chg += 1
print(k, chg)
print(*a)


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
numbers = list(map(int, stdin.readline().split()))
value = [0 for i in range(m + 1)]
ind = n // m
for i in range(n):
	if numbers[i] <= m:
		value[numbers[i]] += 1
queue = []
for i in range(1, m + 1):
	if value[i] < ind:
		for j in range(ind - value[i]):
			queue.append(i)
stdout.write(str(ind) + ' ' + str(len(queue)) + '\n')
for i in range(n):
	if not queue:
		break
	if numbers[i] > m:
		numbers[i] = queue.pop()
	if numbers[i] <= m and value[numbers[i]] > ind:
		value[numbers[i]] -= 1
		numbers[i] = queue.pop()
stdout.write(' '.join(list(map(str, numbers))))


(n, m) = (int(_) for _ in input().split())
a = [int(_) for _ in input().split()]
(x, y) = (n // m, n % m)
cnt = 0
ans = 0
b = [set() for i in range(0, m + 1)]
for i in range(n):
	if a[i] <= m:
		b[a[i]].add(i)
for i in range(1, m + 1):
	while len(b[i]) < x:
		ans += 1
		for j in range(n):
			if a[j] > m or len(b[a[j]]) > x:
				if a[j] <= m:
					b[a[j]].remove(j)
				a[j] = i
				b[i].add(j)
				break
print(x, ans)
print(' '.join((str(i) for i in a)))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
song_band = {song: a[song] for song in range(n)}
buckets = [[] for i in range(m + 1)]
uit = []
for idx in range(n):
	if a[idx] <= m:
		buckets[a[idx]].append(idx)
	else:
		uit.append(idx)
bidx = sorted([i for i in range(m + 1)], key=lambda b: len(buckets[b]))
max_min = n // m
min_ops = 0
l = 1
while l <= m and len(uit) > 0:
	if len(buckets[bidx[l]]) >= max_min:
		l += 1
		continue
	song = uit.pop()
	buckets[bidx[l]].append(song)
	song_band[song] = bidx[l]
	min_ops += 1
r = l
while l <= m and r <= m:
	if len(buckets[bidx[r]]) <= max_min:
		r += 1
	elif len(buckets[bidx[l]]) >= max_min:
		l += 1
	else:
		min_ops += 1
		song = buckets[bidx[r]].pop()
		buckets[bidx[l]].append(song)
		song_band[song] = bidx[l]
print(max_min, min_ops)
print(*[song_band[song] for song in sorted(song_band.keys())])


(n, m) = map(int, input().split())
max_n = n // m
aa = list(map(lambda x: int(x) - 1, input().split()))
cnt = [0] * m
trash = []
for (i, a) in enumerate(aa):
	if a < m and cnt[a] < max_n:
		cnt[a] += 1
	else:
		trash.append(i)
change_cnt = 0
for a in range(m):
	while cnt[a] < max_n:
		cnt[a] += 1
		change_cnt += 1
		aa[trash.pop()] = a
print(max_n, change_cnt)
print(*(x + 1 for x in aa))


def main():
	(n, m) = map(int, input().split())
	n //= m
	l = list(map(int, input().split()))
	cnt = [-n] * (m + 1)
	for a in l:
		if a <= m:
			cnt[a] += 1
	(i, changes) = (-1, 0)
	for a in range(1, m + 1):
		while cnt[a] < 0:
			i += 1
			b = l[i]
			if b <= m:
				if cnt[b] > 0:
					cnt[b] -= 1
				else:
					continue
			l[i] = a
			cnt[a] += 1
			changes += 1
	print(n, changes)
	print(' '.join(map(str, l)))
main()


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [0] * (m + 1)
low = int(n / m)
changes = 0
for i in a:
	if i <= m:
		b[i] += 1
bi = 1
for i in range(n):
	done = False
	while b[bi] >= low:
		bi += 1
		if bi > m:
			done = True
			break
	if done:
		break
	if a[i] > m:
		changes += 1
		a[i] = bi
		b[bi] += 1
	elif b[a[i]] > low:
		b[a[i]] -= 1
		b[bi] += 1
		a[i] = bi
		changes += 1
print(low, changes)
print(' '.join([str(i) for i in a]))


(n, m) = [int(a) for a in input().split()]
a = [int(a) for a in input().split()]
c = [0 for i in range(m)]
minv = 0
maxm = int(n / m)
for i in a:
	if i <= m:
		c[i - 1] += 1
for i in range(len(a)):
	if a[i] > m or c[a[i] - 1] > maxm:
		for j in range(m):
			if c[j] < maxm:
				minv += 1
				c[j] += 1
				if a[i] <= m:
					c[a[i] - 1] -= 1
				a[i] = j + 1
				break
print(maxm, minv)
print(*a)


from collections import Counter
(songs_nr, fav_groups_nr) = (int(x) for x in input().split())
song_idx___group_idx = [int(x) for x in input().split()]
fav_group_idx___songs_nr = {}
for fav_group_idx in range(1, fav_groups_nr + 1):
	fav_group_idx___songs_nr[fav_group_idx] = 0
for group_idx in song_idx___group_idx:
	if group_idx <= fav_groups_nr:
		fav_group_idx___songs_nr[group_idx] += 1
min_max_value = songs_nr // fav_groups_nr
possib_replacements_nr = 0
for song_idx in range(songs_nr):
	group_idx = song_idx___group_idx[song_idx]
	if group_idx <= fav_groups_nr:
		continue
	possib_replacements_nr += 1
for (fav_group_idx, fav_songs_nr) in fav_group_idx___songs_nr.items():
	if fav_songs_nr > min_max_value:
		possib_replacements_nr += fav_songs_nr - min_max_value
replacements_nr = 0
while True:
	curr_group_idx = min(fav_group_idx___songs_nr, key=lambda x: fav_group_idx___songs_nr[x])
	if min(fav_group_idx___songs_nr.values()) >= min_max_value:
		break
	elif replacements_nr == possib_replacements_nr:
		break
	for song_idx in range(songs_nr):
		group_idx = song_idx___group_idx[song_idx]
		if group_idx > fav_groups_nr:
			replacements_nr += 1
			song_idx___group_idx[song_idx] = curr_group_idx
			fav_group_idx___songs_nr[curr_group_idx] += 1
			break
		elif fav_group_idx___songs_nr[group_idx] > min_max_value:
			replacements_nr += 1
			song_idx___group_idx[song_idx] = curr_group_idx
			fav_group_idx___songs_nr[group_idx] -= 1
			fav_group_idx___songs_nr[curr_group_idx] += 1
			break
print(min_max_value, replacements_nr)
print(*song_idx___group_idx)


(n, m) = map(int, input().split())
A = dict()
per = list(map(int, input().split()))
cou = [0] * m
for j in range(n):
	if per[j] <= m:
		cou[per[j] - 1] += 1
ans = 0
ans2 = n // m
s = 0
for j in range(n):
	num = per[j]
	while s <= m - 1:
		if cou[s] < ans2:
			if num > m:
				per[j] = s + 1
				cou[s] += 1
				if cou[s] >= ans2:
					s += 1
				ans += 1
				break
			elif num != s + 1 and cou[num - 1] > ans2:
				cou[num - 1] -= 1
				ans += 1
				cou[s] += 1
				per[j] = s + 1
				if cou[s] >= ans2:
					s += 1
				break
			else:
				break
		else:
			s += 1
	else:
		break
print(ans2, ans)
print(' '.join(map(str, per)))


from collections import Counter
(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
tgt = n // m
b = Counter(a)
rd = sum((b[x] for x in b if x > m))
r = 0
for i in range(1, m + 1):
	while rd and b[i] < tgt:
		for j in range(n):
			if a[j] > m:
				b[a[j]] -= 1
				b[i] += 1
				a[j] = i
				rd -= 1
				r += 1
				break
	while b[i] < tgt:
		for j in range(n):
			if b[a[j]] > tgt:
				b[a[j]] -= 1
				b[i] += 1
				a[j] = i
				r += 1
				break
print(tgt, r)
print(' '.join((str(x) for x in a)))


(n, m) = map(int, input().split())
bands = list(map(int, input().split()))
cnt = {i: 0 for i in range(1, m + 1)}
for b in bands:
	if b <= m:
		cnt[b] += 1
ans = 0
for i in range(n):
	b = bands[i]
	if b > m or cnt[b] > n // m:
		for j in range(1, m + 1):
			if cnt[j] < n // m:
				if b <= m:
					cnt[b] -= 1
				cnt[j] += 1
				bands[i] = j
				ans += 1
				break
print(n // m, ans)
print(*bands)


(n, m) = [int(x) for x in input().split(' ')]
arr = [int(x) for x in input().split(' ')]
d = {}
for i in range(1, m + 1):
	d[i] = 0
av = n // m
for i in arr:
	if i <= m:
		d[i] += 1
ans = 0
for i in range(1, m + 1):
	if d[i] < av:
		for j in range(n):
			if arr[j] <= m:
				if d[arr[j]] > av:
					ans += 1
					d[i] += 1
					d[arr[j]] -= 1
					arr[j] = i
					if d[i] == av:
						break
			else:
				ans += 1
				arr[j] = i
				d[i] += 1
				if d[i] == av:
					break
print(av, ans)
print(' '.join(map(str, arr)))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
count = {}
for i in range(n):
	if a[i] <= m:
		if a[i] in count:
			count[a[i]] += 1
		else:
			count[a[i]] = 1
for i in range(1, m + 1):
	if not i in count:
		count[i] = 0
minB = n // m
minChange = 0

def findChange(a, start, count):
	for i in range(start, n):
		if a[i] > m:
			return i
		elif count[a[i]] > minB:
			count[a[i]] -= 1
			return i
start = -1
for i in range(1, m + 1):
	if count[i] < minB:
		minChange += minB - count[i]
		for j in range(minB - count[i]):
			changePosition = findChange(a, start + 1, count)
			a[changePosition] = i
			count[i] += 1
print(minB, minChange)
for i in range(n):
	print(a[i], end=' ')


cnt = 0
(n, m) = map(int, input().split())
arr = [int(x) for x in input().split()]
prr = [0 for i in range(m)]
k = 0
restindex = []
for i in range(n):
	if arr[i] <= m:
		prr[arr[i] - 1] += 1
		k += 1
	else:
		restindex.append(i)
rest = n - k
p = n // m
trest = n % m
trr = [p for i in range(m)]
(i, j) = (0, 0)
while True:
	if prr[i] > trr[i]:
		j = 0
		suc = 0
		while True:
			if prr[j] < trr[j]:
				prr[i] -= 1
				prr[j] += 1
				arr[arr.index(i + 1)] = j + 1
				cnt += 1
				suc = 1
				if prr[i] == trr[i]:
					break
			j += 1
			if j >= m:
				break
		if suc:
			continue
	i += 1
	if i >= m:
		break
index = 0
for i in range(m):
	while prr[i] < trr[i]:
		prr[i] += 1
		cnt += 1
		arr[restindex[index]] = i + 1
		index += 1
print(n // m, cnt)
s = str(arr[0])
for i in range(1, n):
	s += ' ' + str(arr[i])
print(s)


def music():
	number = [int(x) for x in input().strip().split(' ')]
	src = [int(x) for x in input().strip().split(' ')]
	max_value = number[0] // number[1]
	occurence_dict = dict([(i, src.count(i)) for i in set(src)])
	for i in range(1, number[1] + 1):
		if i not in occurence_dict.keys():
			occurence_dict[i] = 0
	occurence_dict = {k: v for (k, v) in occurence_dict.items() if int(k) <= number[1] and v != max_value}
	result = []
	count = 0
	for item in src:
		if item <= number[1] and item not in occurence_dict.keys():
			result.append(item)
			continue
		elif item in occurence_dict.keys() and occurence_dict[item] <= max_value:
			result.append(item)
			continue
		else:
			v = None
			for (key, value) in occurence_dict.items():
				if value < max_value:
					v = key
					break
			if v == None:
				result.append(item)
				continue
			occurence_dict[v] += 1
			if occurence_dict[v] == max_value:
				del occurence_dict[v]
			if item in occurence_dict.keys():
				occurence_dict[item] -= 1
				if occurence_dict[item] == max_value:
					del occurence_dict[item]
			count += 1
			result.append(v)
	print(str(max_value) + ' ' + str(count))
	print(*result)
music()


a = [int(i) for i in str(input()).split()]
n = a[0]
m = a[1]
a = [int(i) for i in str(input()).split()]
maxmin = n // m
groups = {}
for i in a:
	groups[i] = 0
for i in range(m):
	groups[i + 1] = 0
for i in a:
	groups[i] += 1
changes = 0
for i in range(1, m + 1):
	while groups[i] < maxmin:
		change = False
		for (n, j) in enumerate(a):
			if j <= m:
				continue
			groups[j] -= 1
			a[n] = i
			groups[i] += 1
			changes += 1
			change = True
			if groups[i] >= maxmin:
				break
		if groups[i] >= maxmin:
			continue
		for (n, j) in enumerate(a):
			if groups[j] <= maxmin:
				continue
			groups[j] -= 1
			a[n] = i
			groups[i] += 1
			changes += 1
			change = True
			if groups[i] >= maxmin:
				break
print('%s %s' % (maxmin, changes))
for i in a:
	print(i, end=' ')


import sys
input = sys.stdin.readline

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return res

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(1000000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

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

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
(n, m) = int_array()
a = int_array()
ans = n // m
change = 0
ctr = [0] * 3000
for i in range(n):
	if a[i] <= m:
		ctr[a[i]] += 1
for i in range(1, m + 1):
	change += max(0, ans - ctr[i])
for i in range(n):
	if a[i] > m:
		for j in range(1, m + 1):
			if ctr[j] < ans:
				ctr[j] += 1
				a[i] = j
				break
for i in range(1, m + 1):
	if ctr[i] < ans:
		for j in range(n):
			if ctr[a[j]] > ans:
				ctr[a[j]] -= 1
				a[j] = i
				ctr[i] += 1
			if ctr[i] == ans:
				break
print(*(ans, change))
print(*a)


import sys
(n, m) = map(int, input().split())
liste = list(map(int, input().split()))
roger = n // m
liste2 = []
liste3 = []
compteur = 0
for loop in range(1, m + 1):
	liste2.append(loop)
for loop in range(1, m + 1):
	liste3.append(liste.count(loop))
listeintrus = []
for u in range(n):
	if liste2.count(liste[u]) == 0:
		listeintrus.append(u)
for loop in range(1, m + 1):
	while liste.count(loop) < roger:
		if len(listeintrus) == 0:
			kilo = liste3.index(max(liste3))
			m = liste.index(liste2[kilo])
			liste[m] = loop
			liste3[kilo] -= 1
			liste3[loop - 1] += 1
			compteur += 1
		else:
			liste[listeintrus[0]] = loop
			listeintrus.pop(0)
			liste3[loop - 1] += 1
			compteur += 1
print('{} {}'.format(roger, compteur))
for loop in range(len(liste)):
	print(int(liste[loop]), end=' ')


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
cnt = [0] * (m + 1)
res1 = n // m
for i in arr:
	if i <= m:
		cnt[i] += 1
res2 = 0
for i in range(n):
	if arr[i] > m or (arr[i] <= m and cnt[arr[i]] > res1):
		for j in range(1, m + 1):
			if cnt[j] < res1:
				if arr[i] <= m:
					cnt[arr[i]] -= 1
				cnt[j] += 1
				arr[i] = j
				res2 += 1
				break
print(res1, res2)
print(' '.join(map(str, arr)))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
good = n // m
ans = 0
cnt = [0] * m
ch = [0] * n
for i in range(n):
	if 1 <= a[i] <= m:
		cnt[a[i] - 1] += 1
		if cnt[a[i] - 1] <= good:
			ch[i] = 1
for i in range(m):
	ans += max(0, good - cnt[i])
print(good, ans)
j = 0
for i in range(n):
	if ch[i]:
		continue
	while j < m and good <= cnt[j]:
		j += 1
	if j == m:
		break
	a[i] = j + 1
	cnt[j] += 1
print(*a)


from collections import Counter

def find_artist(songs, m, limit):
	for i in range(1, m + 1):
		if songs[i] < limit:
			return i
	return None
(n, m) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
songs = Counter()
for artist in a:
	songs[artist] += 1
playlist = []
ans = n // m
changes = 0
for artist in a:
	if artist > m or songs[artist] > ans:
		b = find_artist(songs, m, ans)
		if b:
			changes += 1
			playlist.append(b)
			songs[artist] -= 1
			songs[b] += 1
		else:
			playlist.append(artist)
	else:
		playlist.append(artist)
print('{} {}'.format(ans, changes))
print(' '.join((str(artist) for artist in playlist)))


I = lambda : list(map(int, input().split()))
(n, m) = I()
(a, b) = (I(), {})
for band in range(1, m + 1):
	b[band] = 0
for band in a:
	b[band] = b.get(band, 1) + 1
maximum = n // m
minimum = sum([max(0, maximum - b[i]) for i in range(1, m + 1)])
c = [band for band in range(1, m + 1) if b[band] < maximum]
d = []
for band in a:
	if (b[band] > maximum or band > m) and c:
		d.append(c[0])
		b[band] -= 1
		b[c[0]] += 1
		if b[c[0]] == maximum:
			c.pop(0)
	else:
		d.append(band)
print(maximum, minimum)
print(' '.join(map(str, d)))


(n, m) = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
lvl = n // m
b = [0 for _ in range(m)]
for gr in a:
	if gr < m:
		b[gr] += 1
curr = 0
changes = 0
for i in range(n):
	if a[i] < m:
		continue
	while curr < m and b[curr] >= lvl:
		curr += 1
	if curr >= m:
		break
	a[i] = curr
	b[curr] += 1
	changes += 1
if curr < m:
	curr = 0
	for i in range(n):
		if b[a[i]] <= lvl:
			continue
		while curr < m and b[curr] >= lvl:
			curr += 1
		if curr >= m:
			break
		b[a[i]] -= 1
		a[i] = curr
		b[curr] += 1
		changes += 1
print(lvl, changes)
print(' '.join(list(map(lambda x: str(x + 1), a))))


(n, m) = (int(z) for z in input().split())
mas = [int(z) for z in input().split()]
summ = n
summ //= m
ans = 0
s = dict()
for i in range(m):
	s[i + 1] = 0
for i in range(n):
	if mas[i] <= m:
		s[mas[i]] += 1
j = 0
i = 0
while i < m:
	while s[i + 1] < summ:
		if mas[j] > m:
			mas[j] = i + 1
			ans += 1
			s[i + 1] += 1
		elif s[mas[j]] > summ:
			s[mas[j]] -= 1
			mas[j] = i + 1
			ans += 1
			s[i + 1] += 1
		j += 1
	i += 1
print(summ, ans)
print(' '.join((str(z) for z in mas)))


(n, m) = map(int, input().split())
lst = [*map(int, input().split())]
d = {i: 0 for i in range(1, m + 1)}
res = n // m
ans = []
for (i, x) in enumerate(lst):
	if d.get(x) != None:
		if d[x] == res:
			ans.append(i)
		else:
			d[x] += 1
	else:
		ans.append(i)
answer = 0
for x in range(1, m + 1):
	while d[x] < res:
		item = ans.pop()
		lst[item] = x
		d[x] += 1
		answer += 1
print(res, answer)
print(*lst)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
d = dict()
a2 = [0] * n
counter = 0
s = []
ans = n // m
ost = n % m
ost1 = ost
for i in range(m):
	d[i + 1] = 0
for i in range(n):
	if a[i] <= m and d[a[i]] < ans:
		a2[i] = a[i]
		d[a2[i]] += 1
	elif a[i] <= m and d[a[i]] - ost1 < ans:
		a2[i] = a[i]
		d[a2[i]] += 1
		ost1 -= 1
playlist = sorted(d.keys())
for elem in playlist:
	if d[elem] < ans:
		s += [elem] * (ans - d[elem])
j = 0
for i in range(n):
	if a2[i] == 0 and j < len(s):
		counter += 1
		a2[i] = s[j]
		j += 1
	elif a2[i] == 0:
		a2[i] = a[i]
print(ans, counter)
print(*a2)


(n, m) = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
mx = n // m
r = n % m
c = 0
counts = [a.count(i) for i in range(1, m + 1)]
queue = []
for i in range(1, m + 1):
	queue = [i] * (mx - counts[i - 1]) + queue
for i in range(n):
	if a[i] > m:
		if queue:
			curr = queue.pop()
			a[i] = curr
			counts[a[i] - 1] += 1
			c += 1
		else:
			break
for i in range(n):
	if not queue:
		break
	if counts[a[i] - 1] > mx:
		counts[a[i] - 1] -= 1
		a[i] = queue.pop()
		counts[a[i] - 1] += 1
		c += 1
print(mx, c)
print(' '.join([str(item) for item in a]))


(n, m) = [int(i) for i in input().split()]
bands_playing = [int(name) for name in input().split()]
b = dict()
for band in bands_playing:
	if band in b.keys():
		b[band] += 1
	else:
		b[band] = 1
max_min_b = n // m
print(max_min_b, end=' ')
changes = 0
for i in range(m):
	if i + 1 in b.keys():
		changes += max(max_min_b - b[i + 1], 0)
	else:
		changes += max_min_b
		b[i + 1] = 0
print(changes)
for band in bands_playing:
	print_band = band
	if band <= m and b[band] > max_min_b or band > m:
		bands_needed = [band for (band, num) in b.items() if num < max_min_b and band <= m]
		if len(bands_needed) > 0:
			next_band = bands_needed[0]
			b[next_band] += 1
			b[band] -= 1
			print_band = next_band
	print(print_band, end=' ')
print()


MAX_N = 2020
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
deg_A = [0] * MAX_N
res1 = N // M
res2 = 0
for x in A:
	if x <= M:
		deg_A[x] += 1
for (i, val) in enumerate(A):
	if val > M or deg_A[val] > res1:
		min_val = 1 << 30
		x = 0
		for y in range(1, M + 1):
			if deg_A[y] < min_val:
				min_val = deg_A[y]
				x = y
		if deg_A[x] >= res1:
			break
		res2 += 1
		if A[i] <= M:
			deg_A[A[i]] -= 1
		deg_A[x] += 1
		A[i] = x
print(res1, res2)
print(' '.join(map(str, A)))


from collections import defaultdict
(N, M) = map(int, input().split())
ori = list(map(int, input().split()))
best = N // M
c = defaultdict(int)
for o in ori:
	if 1 <= o <= M:
		c[o] += 1
counter = {}
more = set()
less = set()
for i in range(1, M + 1):
	counter[i] = c[i] - best if i in c else -best
	if best < c[i]:
		more.add(i)
	elif best > c[i]:
		less.add(i)
move = 0
for i in range(N):
	if ori[i] not in counter:
		if less:
			k = next(iter(less))
			ori[i] = k
			counter[k] += 1
			if counter[k] == 0:
				less.remove(k)
			move += 1
	elif ori[i] in more:
		if less:
			counter[ori[i]] -= 1
			if counter[ori[i]] == 0:
				more.remove(ori[i])
			k = next(iter(less))
			ori[i] = k
			counter[k] += 1
			if counter[k] == 0:
				less.remove(k)
			move += 1
print(str(best) + ' ' + str(move))
print(' '.join(map(str, ori)))