{-# LANGUAGE BangPatterns #-}

import           Control.Applicative
import           Control.Monad
import qualified Data.ByteString.Char8 as B
import qualified Data.IntMap.Strict    as M
import qualified Data.Sequence         as S

readi :: B.ByteString -> Int
readi bs | Just (n, _) <- B.readInt bs = n

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

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

preOrder :: Tree a -> [a]
preOrder Empty = []
preOrder (Node x l r) = x : preOrder l ++ preOrder r

inOrder :: Tree a -> [a]
inOrder Empty = []
inOrder (Node x l r) = inOrder l ++ [x] ++ inOrder r

solve :: Tree Int -> [[B.ByteString]] -> IO ()
solve _ [] = return ()
solve !t (bs:bss)
    | length bs == 1 = do
        putStrLn . unwords $ fmap show (inOrder t)
        putStrLn . unwords $ fmap show (preOrder t)
        solve t bss
    | otherwise =
        let [_, n] = bs
         in solve (insert (readi n) t) bss

main :: IO ()
main = do
    B.getLine
    xss <- fmap B.words . B.lines <$> B.getContents
    solve Empty xss

