module Main where

--import Debug.Trace
import Data.List

import Control.Monad

solve :: [[Int]] -> [String]
solve l = removeIdx $ sortOn (\(x,_)-> x) $ iter 1 1 (sortOn (\(_, [x,y]) -> x*10^9+y) (addIdx l)) where
    iter _ _ [] = []
    iter cp i ((idx,[p,_]):cs)
        | cp == p   = (idx, (toString p ++ toString i)) : iter p (i+1) cs
        | otherwise = (idx, (toString p ++ toString 1)) : iter p 2 cs

    toString n = iter stn (6 - length stn) where
        iter ac 0 = ac
        iter ac i = iter ('0':ac) (i-1)
        stn = show n

    addIdx = iter 0 where
        iter _ [] = []
        iter i (x:xs) = (i, x):iter (i+1) xs  
    removeIdx = iter where
        iter [] = []
        iter ((_,x):xs) = x:iter xs  
    
readLine:: IO [Int]
readLine = fmap (map read . words) getLine

readLines :: Int -> IO [[Int]]
readLines = flip replicateM readLine

main :: IO() 
main = do
    [n,m] <- readLine
    l <- readLines m
    let ans = solve l
    mapM_ putStrLn ans