import Data.List
import Control.Monad

collect :: Int -> IO [(Int,(Int,Int))]
collect n = zip [1..n] <$> geniof (\(x:y:ls) -> (x,y)) n

cdigit :: Int -> Int
cdigit n | (n`div`10 == 0) = 1
         | otherwise       = 1+(cdigit $ n`div`10)

rewrite :: Int -> [(Int,(Int,Int))] -> [(Int,String)]
rewrite _ [] = []
rewrite c ((a,(p,y)):ls) = let
   id6 = take (6-(cdigit p)) (repeat '0')  ++ (show p) ++ take (6-(cdigit c)) (repeat '0') ++  (show c)
   in if ls == [] || (fst.snd.head $ ls) == p
         then (a,id6) : rewrite (c+1) ls
         else (a,id6) : rewrite 1 ls

lookup2 :: Int -> [(Int,String)] -> (Maybe String,[(Int,String)])
lookup2 _ [] = (Nothing,[])
lookup2 i (x:xs) | fst x == i = (Just $ snd x,xs)
                 | otherwise  = (fst $ lookup2 i xs,x:(snd $ lookup2 i xs))

writedown2 :: Int -> [(Int,String)] -> IO ()
writedown2 _ [] = return ()
writedown2 i (x:xs) = case lookup2 i (x:xs)
  of (Just id6,list) -> putStrLn id6 >> writedown2 (i+1) list
     (Nothing,_)         -> return ()

main :: IO ()
main = do
  [n,m] <- map read.words <$> getLine
  l <- (sortOn $ snd) <$> collect  m
  writedown2 1 $ rewrite 1 l


geniof :: Read a => ([a] -> b) -> Int -> IO [b]
geniof _ 0 = return []
geniof f n = do
  l <- map read <$> words <$> getLine
  ls <- geniof f (n-1)
  return $ (f l):ls

genio :: Read b => Int -> IO [[b]]
genio = geniof id
