import Control.Monad
import Control.Applicative

data Tree a = Nil | Node a (Tree a) (Tree a) deriving(Show)

singleton :: a -> Tree a
singleton x = Node x Nil Nil


insert :: (Ord a) => a -> Tree a -> Tree a
insert x Nil = singleton x
insert x (Node a l r)
  | x <= a    = Node a (insert x l) r
  | otherwise = Node a l (insert x r)

inorder :: Tree a -> [a]
inorder Nil = []
inorder (Node a l r) = [a] ++ inorder l ++ inorder r

preorder :: Tree a -> [a]
preorder Nil = []
preorder (Node a l r) = preorder l ++ [a] ++ preorder r

solver :: [[String]] -> Tree Int -> IO()
solver [] _     = return ()
solver (x:xs) t =
  if head x == "print" then do
    putStrLn $ ' ' : unwords (map show $ preorder t)
    putStrLn $ ' ' : unwords (map show $ inorder t)
    solver xs t
  else -- op == "insert"
    solver xs (insert (read (last x)) t)


main :: IO()
main = do
  m <- (read :: String -> Int) <$> getLine
  inputs <- map words <$> replicateM m getLine
  solver inputs Nil