import           Control.Monad
import           Data.Char
import qualified Data.ByteString.Char8 as B
import           Data.Function
import           Data.List
import           Text.Printf

readInts :: IO [Int]
readInts = unfoldr (B.readInt . B.dropWhile isSpace) <$> B.getLine

main :: IO ()
main = do
  [n, m] <- readInts
  pys <- map (\[p, y] -> (p, y)) <$> replicateM m readInts
  mapM_ putStrLn $ solve n pys

solve :: Int -> [(Int, Int)] -> [String]
solve n
  = map fst
  . sortOn snd
  . map (\(i,(j, (p, _))) -> (printf "%06d%06d" p i, j))
  . join
  . map (zip ([1..] :: [Int]))
  . map (sortOn (snd . snd))
  . groupBy ((==) `on` (fst . snd))
  . sortOn (fst . snd)
  . zip ([1..] :: [Int])
  where
    sortOn f = sortBy (compare `on` f)