import Control.Monad
import Data.List hiding (sortOn)
import Data.Tuple
import Data.Ord
import Data.Function

main :: IO()
main = do
  [n,m] <- readsLn
  pys   <- replicateM m $ pair<$>readsLn
  putStr.unlines.map showID $ solve pys

solve :: [(Int,Int)] -> [(Int,Int)]
solve pys = map snd $ sortOn fst pxs  where
  pxs = concatMap(zipWith (\x(i,(p,_))->(i,(p,x)))[1..])
      $ groupOn (fst.snd) $ sortOn snd $ zip [0..] pys

showID :: (Int,Int) -> String
showID (p,x) = concatMap showN [p,x] where
  showN a = let s = show a in replicate (6-length s) '0' ++ s


readsLn = map read.words<$>getLine
pair (a:b:_) = (a,b)
sortOn f = sortBy(comparing f)
groupOn f = groupBy(\a b->f a==f b)