local n, m = io.read("*n", "*n")
local t = {}
for i = 1, n do
  t[i] = {}
end
local x = {}
local y = {}
local p = {}
for i = 1, m do
  x[i] = 1
  local pi, yi = io.read("*n", "*n")
  y[i] = yi
  p[i] = pi
  table.insert(t[pi], i)
end
for i = 1, n do
  table.sort(t[i], function(a, b) return y[a] < y[b] end)
  for j = 1, #t[i] do
    local z = t[i][j]
    x[z] = j
  end
end
for i = 1, m do
  print(string.format("%06d%06d", p[i], x[i]))
end
