open Printf open Scanf
module Lib = struct
	let i32,i64,ist = Int64.(to_int,of_int,to_string)
	let (+$) = (+) let (-$) = (-) let (/$) = (/) let ( *$) = ( * ) let (%$) = (mod)
	let labs = Int64.abs
	let (+),(-),( * ),(/),(mod),(%) = Int64.(add,sub,mul,div,rem,rem)
	let (+=) r v = r := !r + v
	let (-=) r v = r := !r - v
	let ( *= ) r v = r := !r * v
	let (/=) r v = r := !r / v
	let (%=) r v = r := !r % v
	(* math *)
	let ceildiv p q = (p+q-1L) / q
	let rec gcd m n = match m,n with | m,0L -> m | m,n -> gcd n (m mod n)
	let lcm m n = m / gcd m n * n 
	module I64_infix = struct
		let (land),(lor),(lxor),lnot,(lsl),(lsr),(asr) =
			let open Int64 in
			(logand),(logor),(logxor),lognot,
			(fun u v -> shift_left u (i32 v)),
			(fun u v -> shift_right u (i32 v)),
			(fun u v -> shift_right_logical u (i32 v))
	end
	(* input *)
	let input_i64_array n = Array.init (i32 n) (fun _ -> Scanf.scanf " %Ld" (fun v -> v))
	let get_i64 _ = Scanf.scanf " %Ld" (fun v -> v)
	let get_2_i64 _ = Scanf.scanf " %Ld %Ld" (fun u v -> u,v)
	let get_3_i64 _ = Scanf.scanf " %Ld %Ld %Ld" (fun u v w -> u,v,w)
	let get_4_i64 _ = Scanf.scanf " %Ld %Ld %Ld %Ld" (fun u v w x -> u,v,w,x)
	let get_5_i64 _ = Scanf.scanf " %Ld %Ld %Ld %Ld %Ld" (fun u v w x y -> u,v,w,x,y)
	let i32_get_int _ = Scanf.scanf " %d" (fun v -> v) let i32_get_2_ints _ = Scanf.scanf " %d %d" (fun u v -> u,v) let i32_get_3_ints _ = Scanf.scanf " %d %d %d" (fun u v w -> u,v,w) let i32_get_4_ints _ = Scanf.scanf " %d %d %d %d" (fun u v w x -> u,v,w,x) let i32_get_5_ints _ = Scanf.scanf " %d %d %d %d %d" (fun u v w x y -> u,v,w,x,y)
	(* utils *)
	external id : 'a -> 'a = "%identity"
	let ( *< ) f g x = f (g x)
	let ( *> ) f g x = g (f x)
	let rv f p q = f q p (* ex. 24 |> rv (/) 6 *)
	let alen a = i64 @@ Array.length a
	let llen l = i64 @@  List.length l
	let string_of_list ?(separator=" ") f ls = ls |> List.map f |> String.concat separator
	let string_of_array ?(separator=" ") f a = a |> Array.to_list |> string_of_list ~separator f
	let char_list_of_string str = let rec f0 i a = if i<0 then a else f0 (i-$1) (str.[i]::a) in f0 (String.length str -$ 1) []
	let string_of_char_list ls = List.fold_left (fun u v -> u ^ (String.make 1 v)) "" ls
	let fail _ = failwith "fail"
	let dx,dy = [|1;0;-1;0|],[|0;1;0;-1|]
	let range l r = let ls = ref [] in for i=i32 l to i32 r do ls := i :: !ls done;!ls |> List.rev
	let cartesian_product u v = u |> List.map (fun p -> List.map (fun q -> p,q) v) |> List.flatten
	let shuffle a = Array.sort (fun _ _ -> (Random.int 3) -$ 1) a
	let binary_search ng ok f = let d = if ng < ok then 1L else -1L in
		let rec f0 ng ok =
			if labs (ok - ng) <= 1L then ok
			else let mid = ng + (ok - ng) / 2L in if f mid then f0 ng mid else f0 mid ok
		in f0 (ng-1L*d) (ok+1L*d)
	let lower_bound a v = binary_search 0L (alen a - 1L) (fun i -> a.(i32 i) >= v)
	let upper_bound a v = binary_search 0L (alen a - 1L) (fun i -> a.(i32 i) >  v)
	let equal_range a v = lower_bound a v, upper_bound a v (* #=snd-fst *)
	let rec fix f x = f (fix f) x
	(* imperative *)
	let rep f t ?(stride=1L) fbod = let i = ref f in while !i <= t do fbod !i; i := !i + stride done
	let repb f t ?(stride=1L) fbod = let i,c = ref f,ref true in while !i <= t && !c do
		match fbod !i with | `Break -> c := false | `Ok -> i := !i + stride done
	let repm f t ?(stride=1L) m0 fbod =
		let i,c,m = ref f,ref true,ref m0 in
		while !i<=t && !c do match fbod !m !i with
		| `Break -> c := false | `Break_m m' -> (c := false; m := m') | `Ok m' -> m := m'; i := !i + stride done; !m
	let repi f t ?(stride=1) fbod = let i = ref f in while !i <= t do fbod !i; i := !i +$ stride done
	let repib f t ?(stride=1) fbod = let i,c = ref f,ref true in while !i <= t && !c do
		match fbod !i with | `Break -> c := false | `Ok -> i := !i +$ stride done
	let repim f t ?(stride=1) m0 fbod =
		let i,c,m = ref f,ref true,ref m0 in
		while !i<=t && !c do match fbod !m !i with
		| `Break -> c := false | `Break_m m' -> (c := false; m := m') | `Ok m' -> m := m'; i := !i +$ stride done; !m
	let rep_rev f t ?(stride=1L) fbod = rep t f ~stride @@ fun v -> fbod @@ f + t - v
	let repb_rev f t ?(stride=1L) fbod = repb t f ~stride @@ fun v -> fbod @@ f + t - v
	let repm_rev f t ?(stride=1L) m0 fbod = repm f t ~stride m0 @@ fun u v -> fbod u @@ f + t - v
	let repi_rev f t ?(stride=1) fbod = repi t f ~stride @@ fun v -> fbod @@ f +$ t -$ v
	let repib_rev f t ?(stride=1) fbod = repib t f ~stride @@ fun v -> fbod @@ f +$ t -$ v
	let repim_rev f t ?(stride=1) m0 fbod = repim f t ~stride m0 @@ fun u v -> fbod u @@ f +$ t -$ v
	(* output *)
	let print_list_mle f ls = string_of_list f ls |> print_endline
	let print_array_mle f a = string_of_array f a |> print_endline
	let print_list f ls = ls |> List.iter (fun v -> printf "%s " @@ f v); print_newline ()
	let print_array f a = a |> Array.iter (fun v -> printf "%s " @@ f v); print_newline ()
	(* debug *)
	let dump_2darr f a = a |> Array.iter (fun b -> print_array f b)
	let dump_i64_list ls = print_list ist ls
	let dump_i64_array a = print_array ist a
end open Lib open Array

module IMap =Map.Make(Int64)
let () =
	let n,m = get_2_i64 0 in
	let mp = ref IMap.empty in
	rep 1L m (fun i ->
		let p,y = get_2_i64 0 in
		mp := IMap.add p ((y,i)::(try IMap.find p !mp with Not_found -> [])) !mp;
	);
	let a = make (i32 m) (0L,0L) in
	IMap.iter (fun p ls ->
		List.iteri (fun j (y,i) -> 
			a.(i32 i-$1) <- (p,i64 j+1L)
		) @@ List.sort compare ls
	) !mp;
	iter (fun (p,i) -> 
		printf "%06Ld%06Ld\n" p i
	) a;











Measured memory_bytes: 31528