
import Data.Array (array, elems)
import Data.List (groupBy, sort)
import Control.Monad (forM_)

toSWithPad n x = replicate (n-l) '0' ++ s where
  s = show x
  l = length s

toC [x,y] = (x,y)
tw f x = f (f x)

gp :: [(Int,Int)] -> [[((Int,Int),Int)]]
gp = groupBy (\x y->fst (fst x)==fst (fst y)) . sort . flip zip [0..]

fi cs = go 1 cs where
  go n [] = []
  go n (((pref,year),i):cs) = (i,(pref,n)) : go (n+1) cs

solv n m cs = elems $ array (0,m-1) $ concat [fi cs'| cs' <- gp cs]

main = do
  [n,m] <- map read . words <$> getLine
  cs <- map (toC . map read . words) . lines <$> getContents :: IO [(Int,Int)]
  forM_ (solv n m cs) $ 
    \(pref,n) -> putStr (toSWithPad 6 pref) >> putStrLn (toSWithPad 6 n)
