let n, m = Scanf.scanf " %d %d" @@ fun a b -> a, b
let yps = Array.init m @@ fun i -> Scanf.scanf " %d %d" @@ fun a b -> b, a, i
let rs, ns = Array.make (n + 1) 1, Array.make m ""
let _ = Array.sort compare yps; Array.iter (fun (_, p, i) -> ns.(i) <- Printf.sprintf "%06d%06d" p rs.(p); rs.(p) <- rs.(p) + 1) yps; Array.iter print_endline ns