import Data.List

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+(n`div`10)

rewrite :: Int -> [[(Int,(Int,Int))]] -> [(Int,String)]
rewrite _ [[]] = []
rewrite _ ([]:ls) = rewrite 1 ls
rewrite c (((a,(p,y)):ls):lss) = let
   id6 = take (6-(cdigit p)) (repeat '0')  ++ (show p) ++ take (6-(cdigit c)) (repeat '0') ++  (show c)
   in (a,id6) : rewrite (c+1) (ls:lss)

writedownf :: (a -> String) -> [a] -> IO ()
writedownf _ [] = return ()
writedownf f (x:xs) = putStrLn (f x) >> writedownf f xs

writedown ::  [String] -> IO ()
writedown = writedownf id

main :: IO ()
main = do
  [n,m] <- map read.words <$> getLine
  l <- (groupBy $ \x y -> (fst.snd) x == (fst.snd) y).(sortOn $ snd) <$> collect  m
  writedownf snd $ sortOn fst $ 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
