Scanf.scanf "%d %d\n" (fun n m ->
  let r = Array.make m (0,0) in
  let r2 = Array.make (n+1) [] in
  let r3 = Array.make (n+1) [] in
  for i=0 to m-1 do
     Scanf.scanf "%d %d\n" (fun p1 y1->
       r2.(p1) <- y1::r2.(p1);
       r.(i) <- (p1,y1)
    )
  done;
  for i=0 to n do
    let ls = List.sort (fun x y->x-y) r2.(i) in
    let (_,ls)=List.fold_left(fun (i,l) x -> (i+1,(x,i)::l)) (1,[]) ls in
    r3.(i) <- ls
  done;

  Array.iter (fun (p,y) ->
    let r3 = r3.(p) in
    let n = List.assoc y r3 in
    Printf.printf "%06d%06d\n" p n
  ) r
)