N,M=map(int,input().split())
L=sorted(list(map(int,input().split())))
num=1
m=L[0]
ans=[0]*(m-1)
for i in range(1,len(L)):
    if L[i]==m:
        num+=1
        if i==len(L)-1:
            ans.append(num)
    else:
        ans.append(num)
        ans+=[0]*(L[i]-m-1)
        num=1
        m=L[i]
for i in range(M):
    if len(ans)-1>=i:
        print(i+1,ans[i])
    else:
        print(i+1,0)