{-# LANGUAGE BangPatterns #-}

import Data.Bits
import Data.List
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import qualified Data.ByteString.Char8 as B
import Control.Monad
import Control.Applicative
import Data.Maybe
import Data.Function
import qualified Data.IntMap.Strict as M
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as V
-- import Data.Vector.Unboxed ((!))
import Data.Tuple
import Data.Ord (Down(..))
import Data.Coerce

query :: [(Int, Int)] -> [Int]
query = map snd . sortOn fst . snd . mapAccumL compute (-1,1) .
  sortBy (compare `on` snd) . zip [1..]
  where
    code p k = 10^12 + 10^6 * p + k
    compute (p', k) (j, (p, _))
      | p == p' = ((p, k+1), (j, code p k))
      | True    = ((p, 2), (j, code p 1))

main :: IO ()
main = do
  [n,m] <- map read . words <$> getLine :: IO [Int]
  let conv [x,y] = (x,y) :: (Int, Int)
  pys <- replicateM m $ conv . map read . words <$> getLine
  mapM_ (putStrLn . tail . show) $ query pys
