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: from copy import deepcopy
  from sys import exit, setrecursionlimit
  import math
  from collections import defaultdict, Counter, deque
  from fractions import Fraction as frac
  
  setrecursionlimit(1000000)
  
  
  def main():
      n, m = map(int, input().split())
      py = defaultdict(list)
      si_ban = []
      for _ in range(m):
          x, y = map(int, input().split())
          si_ban.append(y)
          py[x].append(y)
      ans = {}
      for k, v in py.items():
          v.sort()
          for i in range(1, len(v) + 1):
              ans[v[i - 1]] = str(k).zfill(6) + str(i).zfill(6)
      for i in si_ban:
          print(ans[i])
  
  
  def zip(a):
      mae = a[0]
      ziparray = [mae]
      for i in range(1, len(a)):
          if mae != a[i]:
              ziparray.append(a[i])
              mae = a[i]
      return ziparray
  
  
  def is_prime(n):
      if n < 2:
          return False
  
      for k in range(2, int(math.sqrt(n)) + 1):
          if n % k == 0:
              return False
  
      return True
  
  
  def list_replace(n, f, t):
      return [t if i == f else i for i in n]
  
  
  def base_10_to_n(X, n):
      X_dumy = X
      out = ""
      while X_dumy > 0:
          out = str(X_dumy % n) + out
          X_dumy = int(X_dumy / n)
      if out == "":
          return "0"
      return out
  
  
  def gcd(l):
      x = l.pop()
      y = l.pop()
      while x % y != 0:
          z = x % y
          x = y
          y = z
      l.append(min(x, y))
      return gcd(l) if len(l) > 1 else l[0]
  
  
  class Queue:
      def __init__(self):
          self.q = deque([])
  
      def push(self, i):
          self.q.append(i)
  
      def pop(self):
          return self.q.popleft()
  
      def size(self):
          return len(self.q)
  
      def debug(self):
          return self.q
  
  
  class Stack:
      def __init__(self):
          self.q = []
  
      def push(self, i):
          self.q.append(i)
  
      def pop(self):
          return self.q.pop()
  
      def size(self):
          return len(self.q)
  
      def debug(self):
          return self.q
  
  
  class graph:
      def __init__(self):
          self.graph = defaultdict(list)
  
      def addnode(self, l):
          f, t = l[0], l[1]
          self.graph[f].append(t)
          self.graph[t].append(f)
  
      def rmnode(self, l):
          f, t = l[0], l[1]
          self.graph[f].remove(t)
          self.graph[t].remove(f)
  
      def linked(self, f):
          return self.graph[f]
  
  
  class dgraph:
      def __init__(self):
          self.graph = defaultdict(set)
  
      def addnode(self, l):
          f, t = l[0], l[1]
          self.graph[f].append(t)
  
      def rmnode(self, l):
          f, t = l[0], l[1]
          self.graph[f].remove(t)
  
      def linked(self, f):
          return self.graph[f]
  
  
  main()
  
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"}]