#!/usr/bin/ruby
class TLLI
	def initialize
		@trianies=[nil,[0,0,0]]
	end
	def root_triany
		1
	end
	def allocate_triany
		siz=@trianies.size
		@trianies[siz]=[0,0,0]
		return siz
	end
	def set_a(id,value)
		return if !@trianies[id]
		@trianies[id][0]=value
	end
	def set_b(id,value)
		return if !@trianies[id]
		@trianies[id][1]=value
	end
	def set_c(id,value)
		return if !@trianies[id]
		@trianies[id][2]=value
	end
	def get_a(id)
		return if !@trianies[id]
		@trianies[id][0]
	end
	def get_b(id)
		return if !@trianies[id]
		@trianies[id][1]
	end
	def get_c(id)
		return if !@trianies[id]
		@trianies[id][2]
	end
end

class SETI <TLLI # a=>key, b=>left, c=>right
	def set_entry(key)
		x=root_triany
		y=0
		while x!=0&&!(x==root_triany&&get_a(x)==0)
			y=x
			if key<get_a(x)
				x=get_b(x)
			else
				x=get_c(x)
			end
		end
		if y==0
			set_a(root_triany,key)
		else
			leaf=allocate_triany
			set_a(leaf,key)
			if key<get_a(y)
				set_b(y,leaf)
			else
				set_c(y,leaf)
			end
		end
	end
	def find_entry(key)
		t=root_triany
		loop{
			return true if key==get_a(t)
			if key<get_a(t)
				t=get_b(t)
				return false if t==0
			else
				t=get_c(t)
				return false if t==0
			end
		}
	end
	def print2(t)
		return if t==0
		print2(get_b(t))
		Kernel.print(' ') if !@first
		Kernel.print(get_a(t))
		@first=false
		print2(get_c(t))
	end
	def print3(t)
		return if t==0
		Kernel.print(' ') if !@first
		Kernel.print(get_a(t))
		@first=false
		print3(get_b(t))
		print3(get_c(t))
	end
	def print
		@first=true
		print2(root_triany)
		Kernel.puts
		@first=true
		print3(root_triany)
		Kernel.puts
	end
end

dicti=SETI.new
sum=0
gets.to_i.times{
	gets
	if $_[0..0]=='i'
		a=$_.split
		dicti.set_entry(a[1].to_i)
	elsif $_[0..0]=='f'
		a=$_.split
		sum+=dicti.find_entry(a[1].to_i)
	elsif $_[0..0]=='p'
		dicti.print
	end
}