import Prelude
import Data.Maybe (fromJust)
import Data.List (sort, groupBy)

import qualified Data.Map as Map

import Data.Function (on)
import Control.Monad (replicateM, forM)

main :: IO ()
main = do
    [n, m] <- fmap read . words <$> getLine
    pys <- replicateM m $ (\[p, y] -> (p, y)) . fmap read . words <$> getLine
    answer $ solve n m pys

type Answer = [(Int, Int)]
answer :: Answer -> IO ()
answer pxs = do
  _ <- forM pxs $ \(p, x) -> do
    let pad n = inner n (10 ^ (5 :: Int)) (show n)
        inner n d s | n `div` d > 0 = s
                    | otherwise = inner n (d `div` 10) ('0' : s)
    putStrLn $ pad p ++ pad x
  return ()

solve :: Int -> Int -> [(Int, Int)] -> Answer
solve _ _ pys = map (\(p, y) -> (p, fromJust $ Map.lookup p oldnessMapInPref >>= Map.lookup y)) pys
  where
    oldnessMapInPref = Map.fromAscList $ map ((,) . fst . head <*> Map.fromAscList . flip zip [1..] . map snd) $ groupBy ((==) `on` fst) $ sort pys