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



yp_dic={}

yplist=[]

for i in range(M):

  p,y=list(map(int,input().split()))

  if p not in yp_dic:

    yp_dic[p]=[]

  yp_dic[p].append(y)

  yplist.append((y,p))



for key in yp_dic:

  yp_dic[key].sort()



#print(yp_dic)

all_dic={}

for pref,ylist in list(yp_dic.items()):

  pref_dic={}

  for i,y in enumerate(ylist):

    pref_dic[y]=i+1

  all_dic[pref]=pref_dic



#print(all_dic)

for y,p in yplist:

  id="{:0>6}{:0>6}".format(p,all_dic[p][y])

  print(id)

  #print(y,p,all_dic[p][y])

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



yp_dic={}

yplist=[]

for i in range(M):

  p,y=list(map(int,input().split()))

  if p not in yp_dic:

    yp_dic[p]=[]

  yp_dic[p].append(y)

  yplist.append((y,p))



all_dic={}

for key in yp_dic:

  yp_dic[key].sort()

  for i,y in enumerate(yp_dic[key]):

    all_dic[y]=i+1



#print(all_dic)

for y,p in yplist:

  id="{:0>6}{:0>6}".format(p,all_dic[y])

  print(id)

  #print(y,p,all_dic[p][y])

N, M = list(map(int, input().split()))
yp_dic = {}
yplist = []
for i in range(M):
    p, y = list(map(int, input().split()))
    if p not in yp_dic:
        yp_dic[p] = []
    yp_dic[p].append(y)
    yplist.append((y, p))
for key in yp_dic:
    yp_dic[key].sort()
# print(yp_dic)
all_dic = {}
for pref, ylist in list(yp_dic.items()):
    pref_dic = {}
    for i, y in enumerate(ylist):
        pref_dic[y] = i + 1
    all_dic[pref] = pref_dic
# print(all_dic)
for y, p in yplist:
    id = "{:0>6}{:0>6}".format(p, all_dic[p][y])
    print(id)
    # print(y,p,all_dic[p][y])

N, M = list(map(int, input().split()))
yp_dic = {}
yplist = []
for i in range(M):
    p, y = list(map(int, input().split()))
    if p not in yp_dic:
        yp_dic[p] = []
    yp_dic[p].append(y)
    yplist.append((y, p))
all_dic = {}
for key in yp_dic:
    yp_dic[key].sort()
    for i, y in enumerate(yp_dic[key]):
        all_dic[y] = i + 1
# print(all_dic)
for y, p in yplist:
    id = "{:0>6}{:0>6}".format(p, all_dic[y])
    print(id)
    # print(y,p,all_dic[p][y])

+all_dic = {} -# print(yp_dic) -all_dic = {} -for pref, ylist in list(yp_dic.items()): -    pref_dic = {} -    for i, y in enumerate(ylist): -        pref_dic[y] = i + 1 -    all_dic[pref] = pref_dic +    for i, y in enumerate(yp_dic[key]): +        all_dic[y] = i + 1 -    id = "{:0>6}{:0>6}".format(p, all_dic[p][y]) +    id = "{:0>6}{:0>6}".format(p, all_dic[y])