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を取得
  # 初期化
  lists = []
  # listに要素を追加　後で並び変えるため並び替える前の順番を示すキーを第三要素に挿入しておく
  for i in range(M):
      lists.append(list(map(int, input().split())) + [i])
  # 第一要素に昇順で並び替えた後、第二要素で昇順に並び替える
  lists.sort(key=lambda x: x[1])
  lists.sort(key=lambda x: x[0])
  # befは前回の第一要素　stateは第一要素での順位
  bef = 0
  state = 0
  retstr = ""
  triple = []  # 第四要素に識別番号を追加したリストの初期化
  for i in lists:
      if i[0] != bef:
          bef = i[0]
          state = 1
          triple.append(
              [i[0], i[1], i[2], str(i[0]).rjust(6, "0") + str(state).rjust(6, "0")]
          )
      else:
          state += 1
          triple.append(
              [i[0], i[1], i[2], str(i[0]).rjust(6, "0") + str(state).rjust(6, "0")]
          )
  
  triple.sort(
      key=lambda x: x[2]
  )  # 第三要素で並び替えて、元の入力に対応した式ベンツ番号の順番に戻す
  for i in triple:
      print(i[3])  # 識別番号の出力
  
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"}]