output_description: Print the ID numbers for all the cities, in ascending order of indices (City
  1, City 2, ...).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      P_1 Y_1
      :
      P_M Y_M
attempt: N, M = map(int, input().split())                                                                         |N, M = map(int, input().split())
  order = []                                                                                               |order = []
  result = {}                                                                                              |result = {}
  city = {}                                                                                                |city = {}
  for i in range(M):                                                                                       |for i in range(M):
      P, Y = map(int, input().split())                                                                     |    P, Y = map(int, input().split())
      order.append(Y)                                                                                      |    order.append(Y)
      if P in city:                                                                                        |    if P in city:
          city[P].append(Y)                                                                                |        city[P].append(Y)
      else:                                                                                                |    else:
          city[P] = [Y]                                                                                    |        city[P] = [Y]
                                                                                                           |
  s_city = dict(sorted(city.items()))                                                                      |s_city = dict(sorted(city.items()))
  for v in s_city.values():                                                                                |for v in s_city.values():
      v.sort()                                                                                             |    v.sort()
                                                                                                           |
  for k, v in city.items():                                                                                |for k, v in city.items():
      i = 1                                                                                                |    i = 1
      for e in v:                                                                                          |    for e in v:
          order[order.index(e)] = str(k).zfill(8) + str(i).zfill(8)                                        |        order[order.index(e)] = str(k).zfill(8) + str(i).zfill(8)
          i += 1                                                                                           |        i += 1
                                                                                                           |
  for r in order:                                                                                          |for r in order:
      print(r)                                                                                             |    print(r)
  
problem_description: Statement
  
  In Republic of Atcoder, there are N prefectures, and a total of M cities that
  belong to those prefectures.
  
  City i is established in year Y_i and belongs to Prefecture P_i.
  
  You can assume that there are no multiple cities that are established in the
  same year.
  
  It is decided to allocate a 12-digit ID number to each city.
  
  If City i is the x-th established city among the cities that belong to
  Prefecture i, the first six digits of the ID number of City i is P_i, and the
  last six digits of the ID number is x.
  
  Here, if P_i or x (or both) has less than six digits, zeros are added to the
  left until it has six digits.
  
  Find the ID numbers for all the cities.
  
  Note that there can be a prefecture with no cities.
samples: [{"input": "2 3\n    1 32\n    2 63\n    1 12", "output": "000001000002\n    000002000001\n    000001000001\n    \n\n  * As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.\n  * As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.\n  * As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.\n\n* * *"}, {"input": "2 3\n    2 55\n    2 77\n    2 99", "output": "000002000001\n    000002000002\n    000002000003"}]