import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Function

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
toTuple (x : y : _) = (x, y)

main = do
    [n,m] <- getIntList
    pys <- flip zip [1..] . map toTuple <$> replicateM m getIntList
    let ans = map snd . sort . concatMap (zipWith cityNum [1..]) . groupBy ((==) `on` (fst . fst)) $ sort pys
    mapM_ putStrLn ans

cityNum k ((p,y),i) = (i , ((six p) ++ (six k)))
    where six a = let n = length (show a) in drop n ("000000" ++ (show a))