### BUGGY CODE ###

from collections import deque
from enum import Enum, auto

class BinaryTreeNode():
    __slots__ = ['left', 'right', 'val']
    def __init__(self, left=None, right=None, val=None):
        self.left = left
        self.right = right
        self.val = val

class BinarySearchTree():
    def __init__(self):
        self.root = None
        self.nodes = deque([])
        self.num_nodes = 0

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < self.nodes[x].val:
                x = self.nodes[x].left
            else:
                x = self.nodes[x].right
        node = BinaryTreeNode(val=val)

        if y == None:
            self.root = 0
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = self.num_nodes
        else:
            self.nodes[y].right = self.num_nodes
        self.nodes.append(node)
        self.num_nodes += 1

    def preorder(self):
        def preorder_bfs(s):
            print('', self.nodes[s].val, end='')
            if  self.nodes[s].left != None:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None:
                preorder_bfs(self.nodes[s].right)
        preorder_bfs(self.root)
        print('')

    def inorder(self):
        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            if self.nodes[u].left != None:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            print('', self.nodes[u].val, end='')
            if self.nodes[u].right != None:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()

        inorder_dfs_init(self.root)
        print('')

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        bst.inorder()
        bst.preorder()
    else:
        num = int(op[7:])
        bst.insert(num)



### FIXED CODE ###

class BinaryTreeNode():
    # __slots__ = ['left', 'right', 'val']
    def __init__(self, left=None, right=None, val=None):
        self.left = left
        self.right = right
        self.val = val

class BinarySearchTree():
    def __init__(self):
        self.root = None

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < x.val:
                x = x.left
            else:
                x = x.right
        node = BinaryTreeNode(val=val)

        if y == None:
            self.root = node
        elif node.val < y.val:
            y.left = node
        else:
            y.right = node

    def preorder(self):
        self.preorder_list = []
        self.preorder_bfs(self.root)
        return self.preorder_list

    def preorder_bfs(self, u):
        if u == None: return
        self.preorder_list.append(u.val)
        self.preorder_bfs(u.left)
        self.preorder_bfs(u.right)

    def inorder(self):
        self.inorder_list = []
        self.inorder_dfs(self.root)
        return self.inorder_list

    def inorder_dfs(self, u):
        if u == None: return
        self.inorder_dfs(u.left)
        self.inorder_list.append(u.val)
        self.inorder_dfs(u.right)

def print_elements(arr):
    print(' ' + ' '.join([str(item) for item in arr]))

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        print_elements(bst.inorder())
        print_elements(bst.preorder())
    else:
        num = int(op[7:])
        bst.insert(num)