N,M = map(int,input().split())

num_list = list(map(int,input().split()))
num_list = sorted(num_list,reverse = True)

for i in range(1,M+1):
    cnt = 0
    if len(num_list) != 0:
        if i != num_list[-1]:
            print(i,0)
        else:
        
            while i == num_list[-1]:
                num_list.pop()
                cnt += 1
                if len(num_list) == 0:
                    break
            print(i,cnt)
    else:
        print(i,0)