import sys

class BinaryTree:

    def __init__(self):

        self.root = None

    def b_insert(self,x):

        if self.root is None:

            self.root = Node(x)

            return

        node = None

        root = self.root

        while root is not None:

            node = root

            if x == root.data:

                return

            elif x < root.data:

                root = root.left

            else:

                root = root.right

        if node is None:

            # print("center",x)

            node = Node(x)

        elif node.data < x:

            # print("right",x)

            node.right = Node(x)

        else:

            # print("left",x)

            node.left = Node(x)

    def b_inorder(self):

        return inorder(self.root)

    def b_preorder(self):

        return preorder(self.root)

         

class Node:

    def __init__(self,x):

        self.data = x

        self.left = None

        self.right = None

             



def inorder(node):

    nodelist = []

    if node.left:

        nodelist += inorder(node.left)

    nodelist += [node.data]

    if node.right:

        nodelist += inorder(node.right)

    return nodelist

def preorder(node):

    nodelist = [node.data]

    if node.left:

        nodelist += preorder(node.left)

    if node.right:

        nodelist += preorder(node.right)

    return nodelist

 

line = sys.stdin.readline()

bfs = BinaryTree()

 

for temp in sys.stdin:

    if temp[0] == 'i':

        command,num = (n for n in temp.split(" "))

        bfs.b_insert(int(num))

    else:

        print("",end=" ")

        print(*bfs.b_inorder())

        print("",end=" ")

        print(*bfs.b_preorder())

class BinarySearchTree:

    def __init__(self):

        self.root = None



    def insert(self, x):

        node = self.Node(x)

        if self.root is None:

            self.root = node

        else:

            here = self.root

            #

            temp = None

            while here is not None:

                temp = here

                if x < here.node:

                    here = here.left

                elif x > here.node:

                    here = here.right

            if x < temp.node:

                temp.left = node

            elif x > temp.node:

                temp.right = node



    def inorder(self, answer, address = "root"):

        if address is "root":

            address = self.root

        elif address is None:

            return

        self.inorder(answer, address.left)

        answer.append(address.node)

        self.inorder(answer, address.right)



    def preorder(self, answer, address = "root"):

        if address is "root":

            address = self.root

        elif address is None:

            return

        answer.append(address.node)

        self.preorder(answer, address.left)

        self.preorder(answer, address.right)



    class Node:

        def __init__(self, x):

            self.node = x

            self.left = None

            self.right = None



query = int(input())

bt = BinarySearchTree()

for _ in range(query):

    command = input()

    if command[0] == "i":

        bt.insert(int(command.split(" ")[1]))

    else:

        a = []

        bt.inorder(a)

        print(" ", end = "")

        print(*a)

        a = []

        bt.preorder(a)

        print(" ", end = "")

        print(*a)

import sys


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

    def b_insert(self, x):
        if self.root is None:
            self.root = Node(x)
            return
        node = None
        root = self.root
        while root is not None:
            node = root
            if x == root.data:
                return
            elif x < root.data:
                root = root.left
            else:
                root = root.right
        if node is None:
            # print("center",x)
            node = Node(x)
        elif node.data < x:
            # print("right",x)
            node.right = Node(x)
        else:
            # print("left",x)
            node.left = Node(x)

    def b_inorder(self):
        return inorder(self.root)

    def b_preorder(self):
        return preorder(self.root)


class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None


def inorder(node):
    nodelist = []
    if node.left:
        nodelist += inorder(node.left)
    nodelist += [node.data]
    if node.right:
        nodelist += inorder(node.right)
    return nodelist


def preorder(node):
    nodelist = [node.data]
    if node.left:
        nodelist += preorder(node.left)
    if node.right:
        nodelist += preorder(node.right)
    return nodelist


line = sys.stdin.readline()
bfs = BinaryTree()
for temp in sys.stdin:
    if temp[0] == "i":
        command, num = (n for n in temp.split(" "))
        bfs.b_insert(int(num))
    else:
        print("", end=" ")
        print(*bfs.b_inorder())
        print("", end=" ")
        print(*bfs.b_preorder())

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

    def insert(self, x):
        node = self.Node(x)
        if self.root is None:
            self.root = node
        else:
            here = self.root
            #
            temp = None
            while here is not None:
                temp = here
                if x < here.node:
                    here = here.left
                elif x > here.node:
                    here = here.right
            if x < temp.node:
                temp.left = node
            elif x > temp.node:
                temp.right = node

    def inorder(self, answer, address="root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        self.inorder(answer, address.left)
        answer.append(address.node)
        self.inorder(answer, address.right)

    def preorder(self, answer, address="root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        answer.append(address.node)
        self.preorder(answer, address.left)
        self.preorder(answer, address.right)

    class Node:
        def __init__(self, x):
            self.node = x
            self.left = None
            self.right = None


query = int(input())
bt = BinarySearchTree()
for _ in range(query):
    command = input()
    if command[0] == "i":
        bt.insert(int(command.split(" ")[1]))
    else:
        a = []
        bt.inorder(a)
        print(" ", end="")
        print(*a)
        a = []
        bt.preorder(a)
        print(" ", end="")
        print(*a)

-import sys - - -class BinaryTree: +class BinarySearchTree: -    def b_insert(self, x): +    def insert(self, x): +        node = self.Node(x) -            self.root = Node(x) +            self.root = node +        else: +            here = self.root +            # +            temp = None +            while here is not None: +                temp = here +                if x < here.node: +                    here = here.left +                elif x > here.node: +                    here = here.right +            if x < temp.node: +                temp.left = node +            elif x > temp.node: +                temp.right = node + +    def inorder(self, answer, address="root"): +        if address is "root": +            address = self.root +        elif address is None: -        node = None -        root = self.root -        while root is not None: -            node = root -            if x == root.data: -                return -            elif x < root.data: -                root = root.left -            else: -                root = root.right -        if node is None: -            # print("center",x) -            node = Node(x) -        elif node.data < x: -            # print("right",x) -            node.right = Node(x) -        else: -            # print("left",x) -            node.left = Node(x) +        self.inorder(answer, address.left) +        answer.append(address.node) +        self.inorder(answer, address.right) -    def b_inorder(self): -        return inorder(self.root) +    def preorder(self, answer, address="root"): +        if address is "root": +            address = self.root +        elif address is None: +            return +        answer.append(address.node) +        self.preorder(answer, address.left) +        self.preorder(answer, address.right) -    def b_preorder(self): -        return preorder(self.root) +    class Node: +        def __init__(self, x): +            self.node = x +            self.left = None +            self.right = None -class Node: -    def __init__(self, x): -        self.data = x -        self.left = None -        self.right = None - - -def inorder(node): -    nodelist = [] -    if node.left: -        nodelist += inorder(node.left) -    nodelist += [node.data] -    if node.right: -        nodelist += inorder(node.right) -    return nodelist - - -def preorder(node): -    nodelist = [node.data] -    if node.left: -        nodelist += preorder(node.left) -    if node.right: -        nodelist += preorder(node.right) -    return nodelist - - -line = sys.stdin.readline() -bfs = BinaryTree() -for temp in sys.stdin: -    if temp[0] == "i": -        command, num = (n for n in temp.split(" ")) -        bfs.b_insert(int(num)) +query = int(input()) +bt = BinarySearchTree() +for _ in range(query): +    command = input() +    if command[0] == "i": +        bt.insert(int(command.split(" ")[1])) -        print("", end=" ") -        print(*bfs.b_inorder()) -        print("", end=" ") -        print(*bfs.b_preorder()) +        a = [] +        bt.inorder(a) +        print(" ", end="") +        print(*a) +        a = [] +        bt.preorder(a) +        print(" ", end="") +        print(*a)