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

let su =
  xs
  |> List.groupBy (fun xs -> xs.[0]) 
  |> List.map (fun (k,vs) -> k, List.map (fun (ys:int[]) -> ys.[1]) vs)
  |> List.map (fun (k, xs) -> k, List.sort xs)

xs
|> List.iter (fun xs ->
  let tgt = List.find (fun (k,_) -> k = xs.[0]) su |> snd
  let num = tgt
            |> List.findIndex (fun a -> a = xs.[1])
            |> fun x -> x + 1
  printfn "%s%s" (format xs.[0]) (format num)
)



util.Close()
