output_description: If it costs x yen to travel from Station A to Station C, print x.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      X Y
attempt: #!usr/bin/env python3
  from collections import defaultdict
  from collections import deque
  from heapq import heappush, heappop
  import sys
  import math
  import bisect
  import random
  import itertools
  
  sys.setrecursionlimit(10**5)
  stdin = sys.stdin
  
  
  def LI():
      return list(map(int, stdin.readline().split()))
  
  
  def LF():
      return list(map(float, stdin.readline().split()))
  
  
  def LI_():
      return list(map(lambda x: int(x) - 1, stdin.readline().split()))
  
  
  def II():
      return int(stdin.readline())
  
  
  def IF():
      return float(stdin.readline())
  
  
  def LS():
      return list(map(list, stdin.readline().split()))
  
  
  def S():
      return list(stdin.readline().rstrip())
  
  
  def IR(n):
      return [II() for _ in range(n)]
  
  
  def LIR(n):
      return [LI() for _ in range(n)]
  
  
  def FR(n):
      return [IF() for _ in range(n)]
  
  
  def LFR(n):
      return [LI() for _ in range(n)]
  
  
  def LIR_(n):
      return [LI_() for _ in range(n)]
  
  
  def SR(n):
      return [S() for _ in range(n)]
  
  
  def LSR(n):
      return [LS() for _ in range(n)]
  
  
  mod = 1000000007
  
  
  # A
  def A():
      x, y = LI()
      print(x + y // 2)
      return
  
  
  # B
  def B():
      return
  
  
  # C
  def C():
      n, m = LI()
      py = LIR(m)
      pya = py[::1]
      py.sort(key=lambda x: x[1])
      city = [1 for i in range(n)]
      dicity = {}
      for p, y in py:
          dicity[(p, y)] = city[p - 1]
          city[p - 1] += 1
      for p, y in pya:
          a = "00000" + str(p)
          a = a[-6:]
          b = "00000" + str(dicity[(p, y)])
          b = b[-6:]
          print(a + b)
  
      return
  
  
  # D
  def D():
      return
  
  
  # E
  def E():
      return
  
  
  # F
  def F():
      return
  
  
  # G
  def G():
      return
  
  
  # H
  def H():
      return
  
  
  # Solve
  if __name__ == "__main__":
      C()
  
problem_description: Statement
  
  There is a train going from Station A to Station B that costs X yen (the
  currency of Japan).
  
  Also, there is a bus going from Station B to Station C that costs Y yen.
  
  Joisino got a special ticket. With this ticket, she can take the bus for half
  the fare if she travels from Station A to Station B by train and then travels
  from Station B to Station C by bus.
  
  How much does it cost to travel from Station A to Station C if she uses this
  ticket?
samples: [{"input": "81 58", "output": "110\n    \n\n  * The train fare is 81 yen.\n  * The train fare is 58 \u2044 2=29 yen with the 50% discount.\n\nThus, it costs 110 yen to travel from Station A to Station C.\n\n* * *"}, {"input": "4 54", "output": "31"}]