# ????????¢?´¢??¨
class Tree
	# ????????????
	class Node
		def initialize(key, data)
			@key = key
			@data = data
			@left = nil
			@right = nil
		end
		attr_accessor :key, :data, :left, :right
	end
	
	def initialize
		@root = nil
	end
	
	# ????????¢??°
	private

	# ??¢?´¢
	def search(node, key)
		while node
			if key == node.key
				return node
			elsif key < node.key
				node = node.left
			else
				node = node.right
			end
		end
	end
	
	# ?????\
	def insert!(node, key, data)
		if node == nil
			return Node.new(key, data)
		elsif key == node.key
			node.data = data
		elsif key < node.key
			node.left = insert!(node.left, key, data)
		else
			node.right = insert!(node.right, key, data)
		end
		node
	end
	
	# ????°?????????¢???
	def search_min(node)
		node = node.left while node.left
		node
	end
	
	# ?????§????????¢???
	def search_max(node)
		node = node.right while node.right
		node
	end
	
	# ????°???????????????????
	def delete_min!(node)
		return node.right unless node.left
		node.left = delete_min!(node.left)
		node
	end
	
	# ??????
	def delete!(node, key)
		data = nil
		if node
			if key == node.key
				data = node.data
				if node.left == nil
					return node.right, data
				elsif node.right == nil
					return node.left, data
				else
					min_node = search_min(node.right)
					node.key = min_node.key
					node.data = min_node.data
					node.right = delete_min!(node.right)
				end
			elsif key < node.key
				node.left, data = delete!(node.left, key)
			else
				node.right, data = delete!(node.right, key)
			end
		end
		return node, data
	end

	# ???????????¢?´¢
	def precedingOrderSearch(node, &func)
		if node
			func.call(node.key, node.data)
			precedingOrderSearch(node.left, &func)
			precedingOrderSearch(node.right, &func)
		end
	end
	# ???????????¢?´¢
	def afterLineOrderSearch(node, &func)
		if node
			afterLineOrderSearch(node.left, &func)
			afterLineOrderSearch(node.right, &func)
			func.call(node.key, node.data)
		end
	end
	#???????????¢?´¢
	def centerOrderSearch(node, &func)
		if node
			centerOrderSearch(node.left, &func)
			func.call(node.key, node.data)
			centerOrderSearch(node.right, &func)
		end
	end


	# ??¬???????????????
	public

	# ??¢?´¢
	def find(key)
		node = search(@root, key)
		if node
			return	node.data
		else
			return	nil
		end
	end
	
	# ?????\ (??´??°)
	def insert(key, value)
		@root = insert!(@root, key, value)
	end
	
	# ??????
	def delete_key(key)
		@root, data = delete!(@root, key)
		data
	end
	
	# ????°????????±???????
	def min
		if @root
			node = search_min(@root)
			if node
				return node.key, node.data
			end
		end
	end
	
	# ?????§???????±???????
	def max
		if @root
			node = search_max(@root)
			if node
				return node.key, node.data
			end
		end
	end
	
	# ????????????
	def precedingCrawl(&func)
		precedingOrderSearch(@root, &func)
	end

# ????????????
def afterLineCrawl(&func)
	afterLineOrderSearch(@root, &func)
end

# ????????????
def centerCrawl(&func)
	centerOrderSearch(@root, &func)
end


def inspect
	sprintf("#<Tree:%#x>", self.object_id)
end
end
n = gets.to_i
head = nil

n.times do
	num = gets.to_s.chomp!
	if num == "print"
		center = []
		head.centerCrawl do |key, value|
			center << key
		end
		preceding = []
		head.precedingCrawl do |key, value|
			preceding << key
		end

		puts " #{center.join(" ")}"
		puts " #{preceding.join(" ")}"
	else
		num = num.split
		if num[0].to_s == "insert"
			head = Tree.new unless head
			head.insert(num[1].to_i,"dummy")
		elsif num[0].to_s == "delete"
			head.delete_key num[1].to_i 
		else
			puts head.find(num[1].to_i) ?  "yes" : "no"
		end

	end

end

Measured memory_bytes: 110484