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: #!/usr/bin/env python3
  # %% for atcoder uniittest use
  import sys
  
  input = lambda: sys.stdin.readline().rstrip()
  
  
  def pin(type=int):
      return map(type, input().split())
  
  
  def tupin(t=int):
      return tuple(pin(t))
  
  
  def lispin(t=int):
      return list(pin(t))
  
  
  # %%code
  def resolve():
      N, M = pin()  # NofKen,MofSi
      PY = [[] for i in range(N)]
  
      for m in range(M):
          p, y = pin()
          PY[p - 1].append([y, m])
      # print(PY)
      ANS = []
      for i in range(N):
          PY[i].sort(key=lambda x: x[0])
          for n, py in enumerate(PY[i]):
              py[0] = n + 1
              ANS.append([i + 1] + py)
      # print(ANS)
      ANS.sort(key=lambda x: x[2])
  
      # print(ANS)
      PY = ANS
      for k in range(M):
          x, y, z = PY[k]
          X, Y = str(x), str(y)
          t, s = 6 - len(X), 6 - len(Y)
          if t > 0:
              X = "0" * t + X
          if s > 0:
              Y = "0" * t + Y
          print(X + Y)
  
  
  # %%submit!
  resolve()
  
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"}]