{-# 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 qualified Data.Vector.Unboxed.Mutable as VM
import qualified Data.Vector as VB
import qualified Data.Vector.Mutable as VBM
-- import Data.Vector.Unboxed ((!))
import Data.Tuple
import Data.Ord (Down(..))
import Data.Coerce
import GHC.Exts (build)



code :: Int -> Int -> Int
code p k = 10^12 + 10^6 * p + k

{-
query' :: Int -> Int -> V.Vector (Int,Int) -> V.Vector Int
query' n m vec = VB.create $ do
  dictmut <- VBM.replicate n $ IntMap.empty
  V.imapM_ (\i (p,y) -> do entry <- VBM.read dictmut (p-1)
                           VBM.write dictmut (p-1)
                             $! IntMap.insert y i entry) vec
-}  

query :: Int -> Int -> V.Vector (Int,Int) -> V.Vector Int
query n m vec
  = V.replicate m 0 V.// codes
  where
    vec' :: VB.Vector (Int, (Int, Int))
    vec' = VB.convert $ V.imap (\i (p,y) -> (p-1,(y,i))) vec
    dict :: VB.Vector (IntMap Int)
    dict = VB.accumulate (\entry (y,i) -> IntMap.insert y i entry)
            (VB.replicate m IntMap.empty) vec'
    codes :: [(Int,Int)]
    codes = concat $ VB.toList $
      VB.imap (\pm1 -> zipWith (\k i -> (i,code (pm1+1) k)) [1..]
                                 . IntMap.elems) dict 

main :: IO ()
main = do
  [n,m] <- map read . words <$> getLine :: IO [Int]
  rest <- B.getContents
  let vec = V.unfoldrN m (\b -> let (l,r) = B.span (/= '\n') b in
                             Just (decode l, B.tail r)) rest
      decode l = (p,y)
        where Just (p, l1) = B.readInt l
              Just (y, _ ) = B.readInt $ B.dropWhile (== ' ') l1
  V.mapM_ (putStrLn . tail . show) $ query n m vec
