class Node:

    def __init__(self, key):

        self.key = key

        self.parent = None

        self.left = None

        self.right = None



class Tree:



    def __init__(self):

        self.root = None



    def insert(self, node):

        y = None

        x = self.root



        while x is not None:

            y = x

            if node.key <= x.key:

                x = x.left

            else:

                x = x.right



        if y is None:

            self.root = node

        elif node.key < y.key:

            y.left = node

        else:

            y.right = node



    def print_in_order(self, node):

        if node is None:

            return

        self.print_in_order(node.left)

        print(' ' + str(node.key), end='')

        self.print_in_order(node.right)



    def print_pre_order(self, node):

        if node is None:

            return

        print(' ' + str(node.key), end='')

        self.print_pre_order(node.left)

        self.print_pre_order(node.right)



tree = Tree()

m = int(input())

for i in range(m):

    line = input().split()

    if line[0] == 'print':

        tree.print_in_order(tree.root)

        print('')

        tree.print_pre_order(tree.root)

        print('')

    else:

        key = line[1]

        tree.insert(Node(int(key)))

class Node:

    def __init__(self, key):

        self.key = key

        self.parent = None

        self.left = None

        self.right = None

class Tree:

    def __init__(self):

        self.root = None

        self.inorder = []

        self.preorder = []



    def insert(self, node):



        p = None

        x = self.root        

        while x is not None:

            p = x

            # print(node.key, x.key)

            if node.key <= x.key:

                x = x.left

            else:

                x = x.right



        # insertするnodeの親を設定

        node.parent = p



        if p is None:

            self.root = node

        else:

            # insertするnodeを親のleftかrightに設定

            if node.key <= p.key:

                # print('leftに設定')

                p.left = node

            else:

                # print('rightに設定')

                p.right = node





    def print_inorder(self):

        self.inorder = []

        self.inorder_traverse(self.root)

        print((' ' + ' '.join(map(str, self.inorder))))



    def print_preorder(self):

        self.preorder = []

        self.preorder_traverse(self.root)

        print((' ' + ' '.join(map(str, self.preorder))))



    def inorder_traverse(self, node):

        if node is None:

            return

        self.inorder_traverse(node.left)

        self.inorder.append(node.key)

        self.inorder_traverse(node.right)



    def preorder_traverse(self, node):

        if node is None:

            return

        self.preorder.append(node.key)

        self.preorder_traverse(node.left)

        self.preorder_traverse(node.right)



tree = Tree()

m = int(eval(input()))

for i in range(m):

    line = input().split()

    if line[0] == 'print':

        tree.print_inorder()

        tree.print_preorder()

    elif line[0] == 'insert':

        key = int(line[1])

        tree.insert(Node(key))

    # elif line[0] == 'find':

    #     key = int(line[1])

    #     if tree.find(key):

    #         print('yes')

    #     else:

    #         print('no')

    # elif line[0] == 'delete':

    #     print("current tree----")

    #     print(tree.root.key)

    #     print(tree.root.left.key)

    #     print(tree.root.left.right.key)

    #     print("current tree----")

    #     key = int(line[1])

    #     node = tree.find(key)

    #     tree.delete(node)

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None


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

    def insert(self, node):
        y = None
        x = self.root
        while x is not None:
            y = x
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right
        if y is None:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

    def print_in_order(self, node):
        if node is None:
            return
        self.print_in_order(node.left)
        print(" " + str(node.key), end="")
        self.print_in_order(node.right)

    def print_pre_order(self, node):
        if node is None:
            return
        print(" " + str(node.key), end="")
        self.print_pre_order(node.left)
        self.print_pre_order(node.right)


tree = Tree()
m = int(input())
for i in range(m):
    line = input().split()
    if line[0] == "print":
        tree.print_in_order(tree.root)
        print("")
        tree.print_pre_order(tree.root)
        print("")
    else:
        key = line[1]
        tree.insert(Node(int(key)))

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None


class Tree:
    def __init__(self):
        self.root = None
        self.inorder = []
        self.preorder = []

    def insert(self, node):
        p = None
        x = self.root
        while x is not None:
            p = x
            # print(node.key, x.key)
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right
        # insertするnodeの親を設定
        node.parent = p
        if p is None:
            self.root = node
        else:
            # insertするnodeを親のleftかrightに設定
            if node.key <= p.key:
                # print('leftに設定')
                p.left = node
            else:
                # print('rightに設定')
                p.right = node

    def print_inorder(self):
        self.inorder = []
        self.inorder_traverse(self.root)
        print((" " + " ".join(map(str, self.inorder))))

    def print_preorder(self):
        self.preorder = []
        self.preorder_traverse(self.root)
        print((" " + " ".join(map(str, self.preorder))))

    def inorder_traverse(self, node):
        if node is None:
            return
        self.inorder_traverse(node.left)
        self.inorder.append(node.key)
        self.inorder_traverse(node.right)

    def preorder_traverse(self, node):
        if node is None:
            return
        self.preorder.append(node.key)
        self.preorder_traverse(node.left)
        self.preorder_traverse(node.right)


tree = Tree()
m = int(eval(input()))
for i in range(m):
    line = input().split()
    if line[0] == "print":
        tree.print_inorder()
        tree.print_preorder()
    elif line[0] == "insert":
        key = int(line[1])
        tree.insert(Node(key))
    # elif line[0] == 'find':
    #     key = int(line[1])
    #     if tree.find(key):
    #         print('yes')
    #     else:
    #         print('no')
    # elif line[0] == 'delete':
    #     print("current tree----")
    #     print(tree.root.key)
    #     print(tree.root.left.key)
    #     print(tree.root.left.right.key)
    #     print("current tree----")
    #     key = int(line[1])
    #     node = tree.find(key)
    #     tree.delete(node)

+        self.inorder = [] +        self.preorder = [] -        y = None +        p = None -            y = x +            p = x +            # print(node.key, x.key) -        if y is None: +        # insertするnodeの親を設定 +        node.parent = p +        if p is None: -        elif node.key < y.key: -            y.left = node -            y.right = node +            # insertするnodeを親のleftかrightに設定 +            if node.key <= p.key: +                # print('leftに設定') +                p.left = node +            else: +                # print('rightに設定') +                p.right = node -    def print_in_order(self, node): +    def print_inorder(self): +        self.inorder = [] +        self.inorder_traverse(self.root) +        print((" " + " ".join(map(str, self.inorder)))) + +    def print_preorder(self): +        self.preorder = [] +        self.preorder_traverse(self.root) +        print((" " + " ".join(map(str, self.preorder)))) + +    def inorder_traverse(self, node): -        self.print_in_order(node.left) -        print(" " + str(node.key), end="") -        self.print_in_order(node.right) +        self.inorder_traverse(node.left) +        self.inorder.append(node.key) +        self.inorder_traverse(node.right) -    def print_pre_order(self, node): +    def preorder_traverse(self, node): -        print(" " + str(node.key), end="") -        self.print_pre_order(node.left) -        self.print_pre_order(node.right) +        self.preorder.append(node.key) +        self.preorder_traverse(node.left) +        self.preorder_traverse(node.right) -m = int(input()) +m = int(eval(input())) -        tree.print_in_order(tree.root) -        print("") -        tree.print_pre_order(tree.root) -        print("") -    else: -        key = line[1] -        tree.insert(Node(int(key))) +        tree.print_inorder() +        tree.print_preorder() +    elif line[0] == "insert": +        key = int(line[1]) +        tree.insert(Node(key)) +    # elif line[0] == 'find': +    #     key = int(line[1]) +    #     if tree.find(key): +    #         print('yes') +    #     else: +    #         print('no') +    # elif line[0] == 'delete': +    #     print(tree.root.key) +    #     print(tree.root.left.key) +    #     print(tree.root.left.right.key) +    #     key = int(line[1]) +    #     node = tree.find(key) +    #     tree.delete(node)