{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE FlexibleContexts #-}

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)
import Data.STRef.Strict as Ref
import Control.Monad.ST

import Control.Monad
import Control.Monad.Primitive
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Generic.Mutable as VGM
import Data.Bits
import Data.Int
import Data.Word


radSortBy :: (PrimMonad m, VGM.MVector v e)
       => Int               -- ^ the number of passes
       -> Int               -- ^ the size of auxiliary arrays
       -> (Int -> e -> Int) -- ^ the radix function
       -> v (PrimState m) e -- ^ the array to be sorted
       -> m ()
radSortBy passes size rdx arr = do
  tmp    <- VGM.new (VGM.length arr)
  count  <- VPM.new size
  radSort_loop passes rdx arr tmp count
{-# INLINE radSortBy #-}



radSort_loop :: (PrimMonad m, VGM.MVector v e)
          => Int                          -- passes
          -> (Int -> e -> Int)            -- radix function
          -> v (PrimState m) e            -- array to sort
          -> v (PrimState m) e            -- temporary array
          -> VPM.MVector (PrimState m) Int -- radix count array
          -> m ()
radSort_loop passes rdx src dst count = go False 0
 where
 len = VGM.length src
 go swap k
   | k < passes = if swap
                    then radSort_body rdx dst src count k >> go (not swap) (k+1)
                    else radSort_body rdx src dst count k >> go (not swap) (k+1)
   | otherwise  = when swap (VGM.unsafeCopy src dst)
{-# INLINE radSort_loop #-}


radSort_body :: (PrimMonad m, VGM.MVector v e)
     => (Int -> e -> Int)            -- radix function
     -> v (PrimState m) e            -- source array
     -> v (PrimState m) e            -- destination array
     -> VPM.MVector (PrimState m) Int -- radix count
     -> Int                          -- current pass
     -> m ()
radSort_body rdx src dst count k = do
  radSort_countLoop (rdx k) src count
  radSort_accum count
  radSort_moveLoop k rdx src dst count
{-# INLINE radSort_body #-}

radSort_accum :: (PrimMonad m)
           => VPM.MVector (PrimState m) Int -> m ()
radSort_accum count = go 0 0
 where
 len = VPM.length count
 go i acc
   | i < len   = do ci <- VPM.unsafeRead count i
                    VPM.unsafeWrite count i acc
                    go (i+1) (acc + ci)
   | otherwise = return ()
{-# INLINE radSort_accum #-}

radSort_moveLoop :: (PrimMonad m, VGM.MVector v e)
         => Int -> (Int -> e -> Int) -> v (PrimState m) e
         -> v (PrimState m) e -> VPM.MVector (PrimState m) Int -> m ()
radSort_moveLoop k rdx src dst prefix = go 0
 where
 len = VGM.length src
 go i
   | i < len    = do srci <- VGM.unsafeRead src i
                     pf   <- vec_inc prefix (rdx k srci)
                     VGM.unsafeWrite dst pf srci
                     go (i+1)
   | otherwise  = return ()
{-# INLINE radSort_moveLoop #-}


radSort_countLoop :: (PrimMonad m, VGM.MVector v e)
          => (e -> Int)
          -> v (PrimState m) e -> VPM.MVector (PrimState m) Int -> m ()
radSort_countLoop rdx src count = VPM.set count 0 >> go 0
 where
 len = VGM.length src
 go i
   | i < len    = VGM.unsafeRead src i >>= vec_inc count . rdx >> go (i+1)
   | otherwise  = return ()
{-# INLINE radSort_countLoop #-}


vec_inc :: (PrimMonad m, VGM.MVector v Int) => v (PrimState m) Int
  -> Int -> m Int
vec_inc arr i = VGM.unsafeRead arr i
  >>= \e -> VGM.unsafeWrite arr i (e+1) >> return e
{-# INLINE vec_inc #-}



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


query :: Int -> Int -> B.ByteString -> V.Vector Int
query n m rest = V.create $ do
  ret <- VM.new m
  numCinP <- VM.replicate n 0
  V.forM_ dict $ \(j,p,y) -> do
    k <- (+ 1) <$> VM.unsafeRead numCinP (p-1)
    VM.unsafeWrite ret j $ code p k
    VM.unsafeWrite numCinP (p-1) $ k
  return ret
  where
    dict = V.create $ do
      vecInput <- parseInputAsPYs m rest
      radSortBy 4 256
        (\lv -> let sft = lv * 8 in \(j,p,y) -> (y `shiftR` sft) .&. 255)
        vecInput
      return vecInput
  

parseInputAsPYs :: Int -> B.ByteString -> ST s (VM.MVector s (Int, Int, Int))
parseInputAsPYs m input0 = do
  jRef <- Ref.newSTRef 0
  inputRef <- Ref.newSTRef input0
  VM.replicateM m $ do
    j <- Ref.readSTRef jRef
    input <- Ref.readSTRef inputRef
    writeSTRef jRef (j+1)
    let Just (p, input')
          = B.readInt $ B.dropWhile (\x -> x == '\n' || x == ' ') input
        Just (y, input'')
          = B.readInt $ B.dropWhile (== ' ') input'
    writeSTRef inputRef input''
    return (j, p, y)
    
main :: IO ()
main = do
  [n,m] <- map read . words <$> getLine :: IO [Int]
  rest <- B.getContents
  V.mapM_ (putStrLn . tail . show) $ query n m rest


Measured memory_bytes: 11388