import Control.Monad
import Data.Function
import Data.List

main = do
    [_n, m] <- map read . words <$> getLine
    pys <- replicateM m $ (\[p, y] -> (p, y)) . map read . words <$> getLine
    mapM_ putStrLn $ solve pys

-- |
-- >>> solve [(1,32),(2,63),(1,12)]
-- ["000001000002","000002000001","000001000001"]
-- >>> solve [(2,55),(2,77),(2,99)]
-- ["000002000001","000002000002","000002000003"]

solve :: [(Int, Int)] -> [String]
solve pys =
    map addPrefix .
    sortBy (compare `on` snd) .
    concat . 
    map (zipWith (\n ((p, y), i) -> (p * 1000000 + n, i)) [1..]) .
    groupBy ((==) `on` (fst . fst)).
    sort .
    zip pys $ [1..]

addPrefix :: (Int, Int) -> String
addPrefix (n, _) = 
    take 12 $ "00000" ++ (show n)
