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: import sys
  
  array = list(map(int, input().strip().split(" ")))
  
  N = array[0]
  M = array[1]
  
  
  if N < 1:
      sys.exit()
  if N > 10**5:
      sys.exit()
  
  if M < 1:
      sys.exit()
  if M > 10**5:
      sys.exit()
  
  list_t = []
  
  for i in range(M):
  
      array1 = list(map(int, input().strip().split(" ")))
      P = array1[0]
      Y = array1[1]
  
      if P < 1:
          sys.exit()
      if P > N:
          sys.exit()
  
      if Y < 1:
          sys.exit()
      if Y > 10**9:
          sys.exit()
  
      list_t.append([i, P, Y])
  
  
  list_t.sort(key=lambda x: (x[1], x[2]))
  
  
  test_P = list_t[0][1]
  
  list_t[0][2] = 1
  
  bango = 1
  
  
  for j in range(1, M):
  
      test_P_next = list_t[j][1]
  
      if test_P == test_P_next:
          bango = bango + 1
          list_t[j][2] = bango
  
      else:
          bango = 1
          list_t[j][2] = bango
          test_P = test_P_next
  
  list_t.sort(key=lambda x: x[0])
  
  
  for k in range(M):
  
      out1 = str(list_t[k][1])
  
      out_zero1 = out1.zfill(6)
  
      print(out_zero1, end="")
  
      out2 = str(list_t[k][2])
  
      out_zero2 = out2.zfill(6)
  
      print(out_zero2)
  
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"}]