class Node
	attr_accessor :key, :right, :left, :parent
	def initialize(key, right, left, parent)
		@key = key; @right = right; @left = left; @parent = parent
	end
end

$none = Node.new(0, nil, nil, nil)
#$root = Node.new(0, $none, $none, $none)
$root = $none

def insert(k)
	y = $none	
	x = $root
	z = Node.new(k, $none, $none, $none)

	#cnt = 0
	while x != $none
		#puts cnt
		#cnt += 1

		y = x
		if z.key < x.key
			x = x.left
		else
			x = x.right
		end
	end

	z.parent = y
	if y == $none
		$root = z
	else
		if z.key < y.key
			y.left = z
		else
			y.right = z
		end
	end
end

def inorder(u)
	return if u == $none
	inorder(u.left)
	printf(" %d", u.key)
	inorder(u.right)
end

def preorder(u)
	return if u == $none
	printf(" %d", u.key)
	preorder(u.left)
	preorder(u.right)
end

n = gets.to_i
0...n.times do |i|
	line = gets.split
	com = line[0]
	if com == "insert"
		insert(line[1].to_i)
	elsif com == "print"
		inorder($root)
		puts
		preorder($root)
		puts
	end
end