import Control.Applicative ((<$>))
import Control.Monad (foldM)
import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = map B.words <$> B.lines <$> B.getContents >>= solve

solve :: [[ByteString]] -> IO ()
solve bs = foldM f Leaf bs >> return ()
  where f hp [_, bn] = return $ hpInsert (readi B.readInt bn) hp
        f hp [com] | com == end = return hp
                   | otherwise = do
                       let Just (x, hp') = hpView hp
                       print x
                       return hp'
        end = B.pack "end"

data Heap a = Leaf | Node a (Heap a) (Heap a) deriving Show

hpInsert :: (Ord a) => a -> Heap a -> Heap a
hpInsert x hp = hpMergeBy (flip compare) hp (Node x Leaf Leaf)

hpView :: (Ord a) => Heap a -> Maybe (a, Heap a)
hpView hp = hpViewBy (flip compare) hp

hpMergeBy :: (Ord a) => (a -> a -> Ordering) -> Heap a -> Heap a -> Heap a
hpMergeBy _ Leaf Leaf = Leaf
hpMergeBy _ Leaf hp = hp
hpMergeBy _ hp Leaf = hp
hpMergeBy f (Node x xlt xrt) (Node y ylt yrt) =
  case f x y of
   LT -> Node x (hpMergeBy f xrt (Node y ylt yrt)) xlt
   _ ->  Node y (hpMergeBy f yrt (Node x xlt xrt)) ylt

hpViewBy :: (Ord a) => (a -> a -> Ordering) -> Heap a -> Maybe (a, Heap a)
hpViewBy f Leaf = Nothing
hpViewBy f (Node x xlt xrt) = Just (x, hpMergeBy f xlt xrt)

readi :: Integral a =>  (ByteString -> Maybe (a, ByteString)) -> ByteString -> a
readi f s = let Just (n, _) = f s in n

