class BinarySearchTree
	attr_accessor :key, :parent, :left, :right
	@@root = nil
	def initialize(key, parent, left, right)
		self.key = key
		self.parent = parent
		self.left = left
		self.right = right
	end
	
	def self.insert(key)
		if @@root == nil
			@@root = BinarySearchTree.new(key, -1, nil, nil)
		else
			val = @@root
			while true
				if key < val.key
					if val.left
						val = val.left
					else
						val.left = BinarySearchTree.new(key, val.key, nil, nil)
						break
					end
				else
					if val.right
						val = val.right
					else
						val.right = BinarySearchTree.new(key, val.key, nil, nil)
						break
					end
				end
			end
		end
	end
	
	def self.posto(val=@@root)
		Kernel.print " #{val.key}"
		self.posto(val.left) if val.left != nil
		self.posto(val.right) if val.right != nil
	end
	
	def self.ino(val=@@root)
		self.ino(val.left) if val.left != nil
		Kernel.print " #{val.key}"
		self.ino(val.right) if val.right != nil
	end
	
	def self.print
		ino
		Kernel.print "\n"
		posto
		Kernel.print "\n"
	end
	
end


m = gets.chomp.to_i
commands = []
m.times do
	commands.push(gets.chomp)
end
commands.each do |cmd|
	opn, opnd = cmd.split(" ")
	if opnd
		BinarySearchTree.send(opn, opnd.to_i)
	else
		BinarySearchTree.send(opn)
	end
end

