{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns, CPP, LambdaCase, MagicHash                   #-}
{-# LANGUAGE MultiParamTypeClasses, MultiWayIf, OverloadedStrings       #-}
{-# LANGUAGE RecordWildCards, TupleSections, TypeFamilies, ViewPatterns #-}

import           Control.Applicative
import           Control.Exception
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString             as B
import qualified Data.ByteString.Builder     as B
import qualified Data.ByteString.Char8       as C
import qualified Data.ByteString.Internal    as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import qualified Data.Foldable               as F
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import qualified Data.List                   as L
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import           Data.Ratio
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           GHC.Exts
import qualified System.IO                   as IO
import           Unsafe.Coerce

main :: IO ()
main = do
    q <- readLn
    qs <- U.unfoldrN q (runStateT parseQuery) <$> B.getContents
    putStr.unlines.map (\(x,y)->shows x " " ++ show y).U.toList $ solve q qs

solve :: Int -> U.Vector Query -> U.Vector (Int, Int)
solve q qs = runST $ do
    med <- newMedian q
    offset <- UM.replicate 1 0
    res <- newVecStack q
    U.forM_ qs $ \case
        (1, a, b) -> do
            UM.unsafeModify offset (+b) 0
            pushMed a med
        (2, _, _) -> do
            iv <- viewMed med
            o <- UM.unsafeRead offset 0
            push (fmap (+o) iv) res
        _ -> error "invalid query"
    freezeVecStack res

data Median s = Median (UM.MVector s Int) (BinaryHeap s Int) (BinaryHeap s Int)

_smallSum :: Int
_smallSum = 0

_largeSum :: Int
_largeSum = 1

medianVarSize :: Int
medianVarSize = 2

newMedian :: (PrimMonad m) => Int -> m (Median (PrimState m))
newMedian n = Median
    <$> UM.replicate medianVarSize 0
    <*> newBinaryHeap n
    <*> newBinaryHeap n

getMedianSize :: (PrimMonad m) => Median (PrimState m) -> m Int
getMedianSize (Median _ small large) = (+)
    <$> getBinaryHeapSize small
    <*> getBinaryHeapSize large

pushMed :: (PrimMonad m) => Int -> Median (PrimState m) -> m ()
pushMed x med@(Median vars small large) = do
    s <- getMedianSize med
    if s == 0
    then do
        UM.unsafeWrite vars _smallSum (-x)
        insertMinBH (-x) small
    else do
        (m, _) <- viewMed med
        ls <- getBinaryHeapSize small
        ll <- getBinaryHeapSize large
        assert (ls == ll || ls == ll + 1) $ return ()
        if ls == ll
        then case compare x m of
            GT -> do
                top <- unsafeMinViewBH large
                insertMinBH (-top) small
                modifyMinBH large (const x)
                UM.unsafeModify vars (subtract top) _smallSum
                UM.unsafeModify vars (+(x-top)) _largeSum
            _ -> do
                UM.unsafeModify vars (subtract x) _smallSum
                insertMinBH (-x) small
        else case compare x m of
            GT -> do
                UM.unsafeModify vars (+x) _largeSum
                insertMinBH x large
            _ -> do
                top <- negate <$> unsafeMinViewBH small
                insertMinBH top large
                modifyMinBH small (const (-x))
                UM.unsafeModify vars (+(top-x)) _smallSum
                UM.unsafeModify vars (+top) _largeSum

viewMed :: (PrimMonad m) => Median (PrimState m) -> m (Int, Int)
viewMed med@(Median vars small large) = do
    !k <- negate <$> unsafeMinViewBH small
    !s <- (+) <$> UM.unsafeRead vars _smallSum <*> UM.unsafeRead vars _largeSum
    sz <- getMedianSize med
    if even sz
    then return (k, s)
    else return (k, s + k)

type Query = (Int, Int, Int)

parseQuery :: Parser Query
parseQuery = do
    int >>= \case
        1 -> (,,) 1 <$> int <*> int
        2 -> pure (2, 0, 0)
        _ -> error "invalid query"

getVecStackSize :: (PrimMonad m, U.Unbox a)
    => VecStack (PrimState m) a -> m Int
getVecStackSize (VecStack info _) = UM.unsafeRead info 0
{-# INLINE getVecStackSize #-}

freezeVecStack :: (PrimMonad m, U.Unbox a)
    => VecStack (PrimState m) a -> m (U.Vector a)
freezeVecStack (VecStack info s) = do
    len <- UM.unsafeRead info 0
    U.unsafeFreeze $ UM.take len s
{-# INLINE freezeVecStack #-}

-------------------------------------------------------------------------------
-- Utils
-------------------------------------------------------------------------------
rep :: Monad m => Int -> (Int -> m ()) -> m ()
rep !n = U.forM_ $ U.generate n id
{-# INLINE rep #-}
rev :: Monad m => Int -> (Int -> m ()) -> m ()
rev !n = U.forM_ $ U.iterateN n (subtract 1) (n - 1)
{-# INLINE rev #-}
type Parser a = StateT C.ByteString Maybe a
runParser :: Parser a -> C.ByteString -> Maybe (a, C.ByteString)
runParser = runStateT
{-# INLINE runParser #-}
int :: Parser Int
int = coerce $ C.readInt . C.dropWhile isSpace
{-# INLINE int #-}
int1 :: Parser Int
int1 = fmap (subtract 1) int
{-# INLINE int1 #-}
char :: Parser Char
char = coerce C.uncons
{-# INLINE char #-}
byte :: Parser Word8
byte = coerce B.uncons
{-# INLINE byte #-}
-------------------------------------------------------------------------------
-- Data.VecStack
-------------------------------------------------------------------------------
data VecStack s a = VecStack{stackInfo :: !(UM.MVector s Int), stackData :: !(UM.MVector s a)}
newVecStack :: (PrimMonad m, UM.Unbox a) => Int -> m (VecStack (PrimState m) a)
newVecStack n = VecStack <$> UM.replicate 1 0 <*> UM.unsafeNew n
defaultVecStackSize :: Int
defaultVecStackSize = 1024 * 1024
pop :: (PrimMonad m, UM.Unbox a) => VecStack (PrimState m) a -> m (Maybe a)
pop (VecStack info s) = do { len <- UM.unsafeRead info 0; if len > 0 then do { UM.unsafeWrite info 0 (len - 1); pure <$> UM.unsafeRead s (len - 1)} else return Nothing}
{-# INLINE pop #-}
push :: (PrimMonad m, UM.Unbox a) => a -> VecStack (PrimState m) a -> m ()
push x (VecStack info s) = do { len <- UM.unsafeRead info 0; UM.unsafeWrite s len x; UM.unsafeWrite info 0 (len + 1)}
{-# INLINE push #-}
-------------------------------------------------------------------------------
-- Data.Heap.BinaryHeap.Min
-------------------------------------------------------------------------------
data BinaryHeap s a = BinaryHeap (MutVar s Int) (UM.MVector s a)
newBinaryHeap :: (PrimMonad m, U.Unbox a) => Int -> m (BinaryHeap (PrimState m) a)
newBinaryHeap n = BinaryHeap <$> newMutVar 0 <*> UM.new n
getBinaryHeapSize :: (PrimMonad m) => BinaryHeap (PrimState m) a -> m Int
getBinaryHeapSize (BinaryHeap ref _) = readMutVar ref
{-# INLINE getBinaryHeapSize #-}
siftUp :: (PrimMonad m, U.Unbox a, Ord a) => Int -> UM.MVector (PrimState m) a -> m ()
siftUp k vec = do { x <- UM.unsafeRead vec k; flip fix k $ \ loop !i -> if i > 0 then do { let { !parent = (i - 1) `unsafeShiftR` 1}; p <- UM.unsafeRead vec parent; if p <= x then UM.unsafeWrite vec i x else do { UM.unsafeWrite vec i p; loop parent}} else UM.unsafeWrite vec 0 x}
{-# INLINE siftUp #-}
siftDown :: (PrimMonad m, U.Unbox a, Ord a) => Int -> UM.MVector (PrimState m) a -> m ()
siftDown k vec = do { x <- UM.unsafeRead vec k; let { n = UM.length vec}; flip fix k $ \ loop !i -> do { let { !l = unsafeShiftL i 1 .|. 1}; if n <= l then UM.unsafeWrite vec i x else do { let { !r = l + 1}; childL <- UM.unsafeRead vec l; childR <- UM.unsafeRead vec r; if r < n && childR < childL then if x <= childR then UM.unsafeWrite vec i x else do { UM.unsafeWrite vec i childR; loop r} else if x <= childL then UM.unsafeWrite vec i x else do { UM.unsafeWrite vec i childL; loop l}}}}
{-# INLINE siftDown #-}
heapify :: (PrimMonad m, U.Unbox a, Ord a) => UM.MVector (PrimState m) a -> m ()
heapify vec = do { rev (UM.length vec `quot` 2) $ \ i -> do { siftDown i vec}}
{-# INLINE heapify #-}
buildBinaryHeap :: (PrimMonad m, U.Unbox a, Ord a) => U.Vector a -> m (BinaryHeap (PrimState m) a)
buildBinaryHeap vec = do { ref <- newMutVar $ U.length vec; mvec <- U.unsafeThaw vec; heapify mvec; return $! BinaryHeap ref mvec}
{-# INLINE buildBinaryHeap #-}
unsafeMinViewBH :: (PrimMonad m, U.Unbox a) => BinaryHeap (PrimState m) a -> m a
unsafeMinViewBH (BinaryHeap _ vec) = UM.unsafeRead vec 0
{-# INLINE unsafeMinViewBH #-}
minViewBH :: (PrimMonad m, U.Unbox a) => BinaryHeap (PrimState m) a -> m (Maybe a)
minViewBH bh = do { size <- getBinaryHeapSize bh; if size > 0 then Just <$!> unsafeMinViewBH bh else return $! Nothing}
{-# INLINE minViewBH #-}
insertMinBH :: (PrimMonad m, U.Unbox a, Ord a) => a -> BinaryHeap (PrimState m) a -> m ()
insertMinBH x bh@(BinaryHeap info vec) = do { size <- getBinaryHeapSize bh; modifyMutVar' info (+ 1); UM.unsafeWrite vec size x; siftUp size vec}
{-# INLINE insertMinBH #-}
unsafeDeleteMinBH :: (PrimMonad m, U.Unbox a, Ord a) => BinaryHeap (PrimState m) a -> m ()
unsafeDeleteMinBH bh@(BinaryHeap info vec) = do { size <- getBinaryHeapSize bh; modifyMutVar' info (subtract 1); UM.unsafeSwap vec 0 (size - 1); siftDown 0 (UM.unsafeTake (size - 1) vec)}
{-# INLINE unsafeDeleteMinBH #-}
modifyMinBH :: (PrimMonad m, U.Unbox a, Ord a) => BinaryHeap (PrimState m) a -> (a -> a) -> m ()
modifyMinBH bh@(BinaryHeap _ vec) f = do { UM.unsafeModify vec f 0; size <- getBinaryHeapSize bh; siftDown 0 (UM.unsafeTake size vec)}
{-# INLINE modifyMinBH #-}
deleteFindMinBH :: (PrimMonad m, U.Unbox a, Ord a) => BinaryHeap (PrimState m) a -> m (Maybe a)
deleteFindMinBH bh@(BinaryHeap _ vec) = do { size <- getBinaryHeapSize bh; if size > 0 then Just <$!> unsafeMinViewBH bh <* unsafeDeleteMinBH bh else return $! Nothing}
{-# INLINE deleteFindMinBH #-}
clearBH :: (PrimMonad m) => BinaryHeap (PrimState m) a -> m ()
clearBH (BinaryHeap info _) = writeMutVar info 0
freezeInternalBinaryHeapBH :: (PrimMonad m, U.Unbox a) => BinaryHeap (PrimState m) a -> m (U.Vector a)
freezeInternalBinaryHeapBH bh@(BinaryHeap _ vec) = do { size <- getBinaryHeapSize bh; U.unsafeFreeze (UM.unsafeTake size vec)}
