### BUGGY CODE ###


from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None, val=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.val = val
        self.color = Color.WHITE

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

    def set_root(self, val):
        node = BinaryTreeNode(val=val)
        self.root = len(self.nodes)
        self.nodes.append(node)

    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, parent=y)

        if y == None:
            self.set_root(val)
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = len(self.nodes)
            self.nodes.append(node)
        else:
            self.nodes[y].right = len(self.nodes)
            self.nodes.append(node)

    def init_color(self):
        for node in self.nodes:
            node.color = Color.WHITE

    def preorder(self):
        preordered = []
        self.init_color()
        def preorder_bfs(s):
            preordered.append(self.nodes[s].val)
            self.nodes[s].color = Color.GRAY
            if  self.nodes[s].left != None and self.nodes[self.nodes[s].left].color == Color.WHITE:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None and self.nodes[self.nodes[s].right].color == Color.WHITE:
                preorder_bfs(self.nodes[s].right)
                self.nodes[s].color = Color.BLACK
        preorder_bfs(self.root)
        return preordered

    def inorder(self):
        inordered = []
        self.init_color()

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

        def inorder_dfs():
            u = inorder_stack.pop()
            self.nodes[u].color = Color.GRAY
            if self.nodes[u].left != None and self.nodes[self.nodes[u].left].color == Color.WHITE:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            inordered.append(self.nodes[u].val)
            if self.nodes[u].right != None and self.nodes[self.nodes[u].right].color == Color.WHITE:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()
            self.nodes[u].color = Color.BLACK

        inorder_dfs_init(self.root)
        return inordered

def print_elements(ordered):
    for ele in ordered:
        print(' {}'.format(ele), end='')
    print('')

m = int(input())
bst = BinarySearchTree(m)
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)


### 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)