import Control.Applicative
import Control.Monad
import Data.List
import Data.Map.Strict (Map, (!))
import qualified Data.Map.Strict as M
import Text.Printf

main :: IO ()
main = do
  [n, m] <- f
  solve n <$> replicateM m (g <$> f) >>= mapM_ putStrLn
  where
    f = map read <$> words <$> getLine
    g [a, b] = (a, b)

solve :: Int -> [(Int, Int)] -> [String]
solve n pys = let mp = M.unions . map f . groupBy (\(a, _) (b, _) -> a == b) . sort $ pys
              in map (g mp) pys
  where
    f :: [(Int,Int)] -> Map (Int, Int) Int
    f xs = M.fromList $ zip xs [1..]
    g mp y = printf "%06d%06d" (fst y) (mp ! y)
