import Control.Monad
import Text.Printf

main :: IO ()
main = do
  [n,m] <- getInts
  pys <- replicateM m $ do
    [p,y] <- getInts
    return (p,y)
  putStr . unlines $ solve pys

getInts :: IO [Int]
getInts = map read . words <$> getLine

format :: (Int,Int) -> String
format (p,i) = printf "%06d%06d" p i

solve :: [(Int,Int)] -> [String]
solve cs = [format (p, 1 + rank p y) | (p,y) <- cs]
  where
    rank p0 y0 = length $ filter (\(p1,y1) -> p0 == p1 && y1 < y0) cs
