local ior = io.input()
local n, m = ior:read("*n", "*n")
local tbl = {}
for i = 1, m do
  local p, y = ior:read("*n", "*n")
  table.insert(tbl, {i, p, y})
end
table.sort(tbl, function(x, y)
  if x[2] ~= y[2] then
    return x[2] < y[2]
  else
    return x[3] < y[3]
  end
end
)

local curp = 0
local cury = 0
for i = 1, m do
  if curp ~= tbl[i][2] then
    cury = 0
    curp = tbl[i][2]
  end
  cury = cury + 1
  tbl[i][3] = cury
end

table.sort(tbl, function(x, y)
  return x[1] < y[1]
end
)

for i = 1, m do
  io.write(string.format("%06d", tbl[i][2]))
  io.write(string.format("%06d", tbl[i][3]))
  io.write("\n")
end
