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: interview

Starter code:

Solutions:
#!/usr/bin/env python3

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 = list(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)


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):
            #print(j)
            if j <= m:
                continue
            groups[j]-=1
            a[n]=i
            groups[i]+=1
            #print('kek')
            changes+=1
            change=True
            if groups[i]>=maxmin:
                break
        
        if groups[i]>=maxmin:
            continue

        for n,j in enumerate(a):
            #print(j)
            if groups[j]<=maxmin:
                continue
            #print(groups[j])
            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=' ')


n, m = list(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 = 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:
            #print("in")
            #print(len(a))
            #print(lbig[0])
            a[lbig[0]]=i
            lbig.pop(0)
            #print('out');
        count[i]+=1
print(str(n//m)+' '+str(ans))
for i in a:
    print(i,end=' ')