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 | Delete Int | Find Int | Insert Int deriving (Show)
data Order = Preorder | Inorder deriving (Eq, Show)

sDelete = B.pack "delete"
sFind   = B.pack "find"
sInsert = B.pack "insert"
sPrint  = B.pack "print"

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

    delete x = iter where
        iter Nil = Nil 
        iter (Node y l r)             
            | x < y  = Node y (iter l) r
            | x > y  = Node y l (iter r)
            | x == y = case (l, r) of
                (Nil, Nil) -> Nil
                (Nil, r)   -> r
                (l, Nil)   -> l
                (l, r)     -> Node z l (delete z r) where
                    z = min r
    
    min (Node x Nil _) = x
    min (Node x l   _) = min l

    find x = iter where
        iter (Node y l r)
            | x == y = "yes"
            | x <  y = iter l
            | x >  y = iter r 
        iter Nil = "no"

    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 = toString . (toList Preorder)
    inorder  = toString . (toList Inorder)

toList :: Ord a => Order -> Tree a -> [a]
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

toString:: [Int] -> String
toString [] = []
toString (x:xs) = ' ':(show x)++ toString xs

toInt :: B.ByteString -> Int
toInt = fst . fromJust . B.readInt
                    
readIntLn:: IO Int
readIntLn = toInt <$> B.getLine

readCommand:: IO Command
readCommand = do
    l <- B.words <$> B.getLine
    return $ case l of
        [cmd, n]
            | cmd == sDelete -> Delete $ toInt n
            | cmd == sFind   -> Find   $ toInt n
            | cmd == sInsert -> Insert $ toInt n
        [sPrint]     -> Print

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

