{-# LANGUAGE ScopedTypeVariables,Rank2Types #-}


import Data.Array.ST
import Data.Array
import Data.STRef
import Control.Monad.ST
import Control.Monad

--head,tail,size,bodyArray
type Queue s a = (STRef s (Int,Int,Int),STArray s Int (Maybe a))

new_queue::Int->ST s (Queue s a)
new_queue size = do
  ar<-newArray (0,size-1) Nothing
  hts_pt<-newSTRef (0,0,size)
  return (hts_pt,ar)

is_empty::Queue s a -> ST s Bool
is_empty (hts_pt,ar) = do
  (h,t,s)<-readSTRef hts_pt
  return (if h==t then True else False)

is_full::Queue s a -> ST s Bool
is_full (hts_pt,ar) = do
  (h,t,s)<-readSTRef hts_pt
  return (if mod (t+1) s == h then True else False)

de_queue::Queue s a -> ST s a
de_queue (hts_pt,ar) = do
  (h,t,s)<-readSTRef hts_pt
  (Just v)<-readArray ar h
  writeArray ar h Nothing
  writeSTRef hts_pt (mod (h+1) s,t,s)
  return v

en_queue::a -> Queue s a -> ST s ()
en_queue v (hts_pt,ar) = do
  (h,t,s)<-readSTRef hts_pt
  writeArray ar t (Just v)
  writeSTRef hts_pt (h,mod (t+1) s,s)
  return ()

show_queue::Queue s a -> ST s (Maybe (Array Int (Maybe a)))
show_queue (hts_pt,ar) = do
  b<-is_empty (hts_pt,ar)
  if b then return Nothing else do
                              iar<-freeze ar
                              return (Just iar)

--キュー、プロセス単位、現在時、完了履歴
do_proc::Queue s (String,Int) -> Int -> Int ->ST s [(String,Int)]
do_proc queue quant now = do
  b<-is_empty queue
  if b then return []
       else do
         (p_name,p_time) <- de_queue queue
         if p_time <= quant then do
              rest<-do_proc queue quant (now+p_time)
              return ((p_name,now+p_time):rest)
                            else do
              en_queue (p_name,p_time-quant) queue
              rest<-do_proc queue quant (now+quant)
              return rest

make_schedule::Int->[(String,Int)]->ST s (Queue s (String,Int))
make_schedule n ls = do
  queue<-new_queue n
  forM_ ls (\ i -> en_queue i queue)
  return queue


n_get::Int->IO [(String,Int)]
n_get 0 = return []
n_get n =do
  ptc<-getLine
  let p=head (words ptc)
  let t=read (last (words ptc))
  rest<-n_get (n-1)
  return ((p,t):rest)

main::IO()
main=do
  nqc<-getLine
  let n:q:[] = map read (words nqc)
  dat<-n_get n
  let trace = runST $ do
                queue<-make_schedule 100000 dat
                tr<-do_proc queue q 0
                return tr
  forM_ trace print_ls

print_ls::(String,Int)->IO()
print_ls (p,t) = do
  putStr (p++" ")
  print t
