{-# LANGUAGE BangPatterns, MultiWayIf #-}

import Control.Applicative
import Control.Monad
import Data.List
import Debug.Trace (traceShow, traceShowM)

import qualified Data.ByteString.Char8 as B
import Text.Printf (printf)
import Control.Monad.ST
import Data.Array.ST
import Data.Array
import qualified Data.IntMap.Strict as M

readi b | Just (n, _) <- B.readInt b = n

f1 xs = [(j, k, i) | (i, (j, k)) <- zip [1..] xs]

solve :: Int -> Int -> [(Int, Int)] -> IO ()
solve n m pys = forM_ pys $ \(i, j) -> do
    let m = ary ! i
    let a = m M.! j
    printf "%06d%06d\n" i (a :: Int)
  where
    ps = groupBy (\a b -> fst a == fst b) $ sort pys
    ary = runSTArray $ do
        a <- newArray (1, n) M.empty
        let qs = fmap f1 ps
        forM_ qs $ \gs -> do
            forM_ gs $ \(i, j, k) -> do
                m <- readArray a i
                writeArray a i (M.insert j k m)
        return a

main :: IO ()
main = do
    [n, m] <- fmap readi . B.words <$> B.getLine :: IO [Int]
    pys <- replicateM m $ do
        [p, y] <- fmap readi . B.words <$> B.getLine
        return (p, y) :: IO (Int, Int)
    solve n m pys