open Hashtbl
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 g s = String.(make (6 - length s) '0' ^ s)
let f a b = g (string_of_int a) ^ g (string_of_int b)
let h, ns = create n, Array.make m ""
let _ = Array.sort (fun x y -> compare y x) yps; Array.iteri (fun _ (_, p, i) -> replace h p @@ try (i, p) :: find h p with _ -> [(i, p)]) yps;
  iter (fun _ xs -> List.iteri (fun j (i, p) -> ns.(i) <- f p (j + 1)) xs) h; Array.iter print_endline ns