type ABC(stream:System.IO.TextReader) =
  member this.Scan1 f = stream.ReadLine() |> f
  member this.Scan2 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1]))
  member this.Scan3 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2]))
  member this.Scan4 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2], a.[3]))
  member this.ScanVecH f = stream.ReadLine().Split() |> Array.map f
  member this.ScanVecV n f = [ for i in 1..n -> stream.ReadLine() |> f ]
  member this.ScanMatrix n f  = [ for i in 1..n do yield stream.ReadLine().Split() |> Array.map f ]
  member this.ScanCharMatrix n = [| for i in 1..n -> stream.ReadLine().ToCharArray() |]
  member this.Close () = stream.Close()

let util = ABC(stdin)

let format n = (string n).PadLeft(6, '0')
 
let N, M = util.Scan2 int
let xs = util.ScanMatrix M int

xs
|> List.mapi (fun i -> fun x -> i, x.[0], x.[1])
|> List.groupBy (fun (_,a,_) -> a) 
|> List.collect (fun (_,block) ->
    block
    |> List.sortBy (fun (_,_,a) -> a) // 県内でソートして
    |> List.mapi (fun i -> fun (x,a,_) -> x, (format a) + (format (i+1)) ) // 名前に変換
   ) // bind/collect して平坦化
|> List.sortBy fst // 出力順序を調整して
|> List.map snd
|> String.concat "\n" // 文字列は先に作っておいて pirntfn 呼び出し回数を削減
|> printfn "%s"

util.Close()