import Control.Applicative
import Control.Monad.State

data Tree a = Nill | Tree a (Tree a) (Tree a) deriving (Show)

main = do
        n <- readLn
        evalStateT (query n) Nill

insert :: Ord a => a -> Tree a -> Tree a
insert x Nill = Tree x Nill Nill
insert x (Tree y l r)
    | x < y = Tree y (insert x l) r
    | x > y = Tree y l (insert x r)
    | otherwise = Tree y l r

searchITW Nill = []
searchITW (Tree x l r) = searchITW l ++ [x] ++ searchITW r

searchPTW Nill = []
searchPTW (Tree x l r) = x : (searchPTW l ++ searchPTW r)

type Query s = StateT s IO ()

query n
    | n == 0 = return ()
    | otherwise = do
        inp <- liftIO $ words<$>getLine
        case head inp of
            "insert" -> let x = read (inp !! 1) :: Int in qInsert x >> query (n-1)
            "print"  -> qPrint >> query (n-1)
            _        -> return ()

qInsert :: Ord a => a -> Query (Tree a)
qInsert x = modify (insert x)
qPrint = do
        t <- get
        liftIO $ putStrLn.unwords.map show $ searchITW t
        liftIO $ putStrLn.unwords.map show $ searchPTW t