import Control.Applicative ((<$>))
import Control.Monad.State
import Data.Monoid

data Tree a = Nill | Tree a (Tree a) (Tree a) deriving (Show)
newtype DList a = DList { unDL :: [a] -> [a] }

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 tree = fromDList $ sitw tree

sitw Nill = mempty
sitw (Tree x l r) = sitw l `mappend` toDList [x] `mappend` sitw r

searchPTW tree = fromDList $ sptw tree

sptw Nill = mempty
sptw (Tree x l r) = toDList [x] `mappend` sptw l `mappend` sptw r

find :: Ord a => a -> Tree a -> Bool
find x Nill = False
find x (Tree y l r)
    | x > y = find x r
    | x < y = find x l
    | x == y = True

delete :: Ord a => a -> Tree a -> Tree a
delete x Nill = Nill
--delete x t@(Tree y Nill Nill)
--    | x /= y = t
--    | x == y = Nill
--delete x t@(Tree y l Nill)
--    | x > y = t
--    | x < y = Tree y (delete x l) Nill
--    | x == y = l
--delete x t@(Tree y Nill r)
--    | x > y = Tree y Nill (delete x r)
--    | x < y = t
--    | x == y = r
--delete x t@(Tree y l r)
--    | x < y  = Tree y (delete x l) r
--    | x > y  = Tree y l (delete x r)
--    | x == y = Tree z l (delete z r)
--        where (Tree z _ _) = r
delete x (Tree y l r)
    | x < y = Tree y (delete x l) r
    | x > y = Tree y l (delete x r)
    | x == y = delete' l r
        where delete' l' Nill = l'
              delete' Nill r' = r'
              delete' l' r' = Tree x' l' (delete x' r)
                where (Tree x' _ _) = 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)
            "find"   -> let x = read (inp !! 1) :: Int in qFind x >> query (n-1)
            "delete" -> let x = read (inp !! 1) :: Int in qDelete x >> 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
qFind :: Ord a => a -> Query (Tree a)
qFind x = do
        t <- get
        if find x t then liftIO $ putStrLn "yes"
                    else liftIO $ putStrLn "no"
qDelete :: Ord a => a -> Query (Tree a)
qDelete x = modify (delete x)


toDList :: [a] -> DList a
toDList xs = DList (xs++)

fromDList (DList f) = f []

instance Monoid (DList a) where
        mempty  = DList (\xs -> [] ++ xs)
        (DList f) `mappend` (DList g) = DList (\xs -> f (g xs))