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 i != num_list[-1]:
        print(i,0)
    else:
        
        while i == num_list[-1]:
            num_list.pop()
            cnt += 1
        print(i,cnt)