
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as C
import Debug.Trace
import Data.List
import Data.Ord
import Control.Monad


r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine

data City = C { num :: Int,
                pref :: Int,
                year :: Int } deriving Show

main :: IO ()
main = do
    [n,m] <- r'
    pys <- V.generateM m (\i -> do
        [p,y] <- r'
        return C {num = i, pref = p, year = y}
        )
    let srtd = sortBy (comparing pref `mappend` comparing year) (V.toList pys)
    let rnkd = rankize (pref (head srtd), 1) srtd
    let fin  = sortOn (num.fst) rnkd
    mapM_ (C.putStrLn . showCity) fin

rankize :: (Int, Int) -> [City] -> [(City, Int)]
rankize _ [] = []
rankize (cPref, ac) (city:xs)
    | pref city==cPref  = (city,ac):(rankize (pref city,ac+1) xs)
    | otherwise         = (city,1 ):(rankize (pref city, 1+1) xs)

showCity :: (City,Int) -> C.ByteString
showCity (city,rank) =
    let pS = C.pack $ show (pref city)  :: C.ByteString
        rS = C.pack $ show rank         :: C.ByteString
        pI = 6 - (C.length pS)          :: Int 
        rI = 6 - (C.length rS)          :: Int
    in  C.concat [  (C.replicate pI '0'), pS, 
                    (C.replicate rI '0'), rS ]

