import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import Text.Printf
import Data.Ord

main :: IO ()
main = readLine >>= main'
    where
        main' [n, m] = replicateM m readLine >>= printRes . solve 
        printRes = mapM_ (\[x, y] -> printf "%06d%06d\n" x y)

solve :: [[Int]] -> [[Int]]
solve = map snd . sortBy (comparing fst) . makeIDs 1 . sortBy cmpf . zip [0..]
    where
        cmpf lhs rhs = comparing (head . snd) lhs rhs  `mappend` comparing (last . snd) lhs rhs

        makeIDs np xxs@(_ : _) = innerMIDs 1 xxs
            where
                innerMIDs m (x@(n, [p, _]) : xs)
                    | np == p = (n, [p, m]) : innerMIDs (m + 1) xs
                    | otherwise = makeIDs (np + 1) $ x : xs
                innerMIDs _ _ = []
        makeIDs _ _ = []


readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

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