module Main where

-- import Debug.Trace
import Data.List
import qualified Data.Sequence as S
import qualified Data.ByteString.Char8 as B
import Data.Int
import Data.Char
import Data.Array
import Data.Maybe
import qualified Data.Map as M
import Data.Ord
import Data.Functor
import Control.Applicative
import Control.Monad
import Text.Printf

data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show)
data Command = Print | Insert Int deriving (Show)
data Order = Preorder | Inorder deriving (Eq, Show)

sInsert = B.pack "insert"
sPrint  = B.pack "print"

solve :: [Command] -> [([Int], [Int])]
solve = iter Nil where
    iter :: Tree Int-> [Command] -> [([Int], [Int])]
    iter _ [] = []
    iter rt (c:cs) = case c of
        Print    -> (preorder rt, inorder rt):(iter rt cs)
        Insert x -> iter (insert x rt) cs

    insert x = iter where
        iter (Node y l r)             
                | x < y     = Node y (iter l) r
                | otherwise = Node y l (iter r) 
        iter Nil = Node x Nil Nil 

    preorder = toList Preorder
    inorder  = toList Inorder
    toList ord = iter where
        iter Nil = []
        iter (Node id l r)
            | ord == Preorder = id:(iter l) ++ iter r
            | ord == Inorder  = (iter l) ++ id:iter r
            
readIntLn:: IO Int
readIntLn = (fst . fromJust . B.readInt) <$> B.getLine

readCommand:: IO Command
readCommand = do
    l <- B.words <$> B.getLine
    return $ case l of
        [sInsert, n] -> Insert $ (fst . fromJust) (B.readInt n)
        [sPrint]     -> Print

printl:: [Int] -> IO ()
printl [] = putStrLn ""
printl (x:xs) = do
    putStr $ ' ':(show x)
    printl xs

print':: [([Int], [Int])] -> IO ()
print' [] = return ()
print' ((x, y):xs) = do
    printl y
    printl x
    print' xs

main :: IO() 
main = do
    n <- readIntLn
    l <- replicateM n readCommand
    print' $ solve l

