import sys



class Node():

    def __init__(self, parent = -1, left = -1, right = -1):

        self.parent = parent

        self.left = left

        self.right = right

        

    def __eq__(self, other):

        if self.num == other.num:

            return True

        else:

            return False



def insert(node, z):

    global root

    p = -1

    x = root

    while x != -1:

        p = x

        if z < x:

            x = node[x].left

        else:

            x = node[x].right

    

    if p == -1:

        root = z

        node[z] = Node()

    elif z < p:

        node[p].left = z

        node[z] = Node(p)

    else:

        node[p].right = z

        node[z] = Node(p)

        

def preorder(node, i):

    print(" " + str(i), end ="")

    if node[i].left != -1:

        preorder(node, node[i].left)

    if node[i].right != -1:

        preorder(node, node[i].right)



def inorder(node, i):

    if node[i].left != -1:

        inorder(node, node[i].left)

    print(" " + str(i), end ="")

    if node[i].right != -1:

        inorder(node, node[i].right)

        

input()

node = {}

root = -1

for s in sys.stdin:

    if s[0] == "p":

        inorder(node, root)

        print()

        preorder(node, root)

        print()

    else:

        insert(node, int(s[7:]))



import sys



class Node():

    __slots__ = ['key', 'left', 'right']

    def __init__(self, key):

        self.key = key

        self.left, self.right = None, None

        

    def __str__(self):

        return self.key



root = None

def insert(z):

    global root

    x, y = root, None

    while x:

        y = x

        if z < x.key:

            x = x.left

        else:

            x = x.right

    

    if y == None:

        root = Node(z)

    elif z < y.key:

        y.left = Node(z)

    else:

        y.right = Node(z)

        

def preorder(x):

    return f" {x.key}" + preorder(x.left) + preorder(x.right) if x else ""



def inorder(x):

    return inorder(x.left) + f" {x.key}" + inorder(x.right) if x else ""

        

eval(input())

node = {}

for s in sys.stdin:

    if s[0] == "p":

        pass

        print((inorder(root)))

        print((preorder(root)))

    else:

        insert(int(s[7:]))

import sys


class Node:
    def __init__(self, parent=-1, left=-1, right=-1):
        self.parent = parent
        self.left = left
        self.right = right

    def __eq__(self, other):
        if self.num == other.num:
            return True
        else:
            return False


def insert(node, z):
    global root
    p = -1
    x = root
    while x != -1:
        p = x
        if z < x:
            x = node[x].left
        else:
            x = node[x].right
    if p == -1:
        root = z
        node[z] = Node()
    elif z < p:
        node[p].left = z
        node[z] = Node(p)
    else:
        node[p].right = z
        node[z] = Node(p)


def preorder(node, i):
    print(" " + str(i), end="")
    if node[i].left != -1:
        preorder(node, node[i].left)
    if node[i].right != -1:
        preorder(node, node[i].right)


def inorder(node, i):
    if node[i].left != -1:
        inorder(node, node[i].left)
    print(" " + str(i), end="")
    if node[i].right != -1:
        inorder(node, node[i].right)


input()
node = {}
root = -1
for s in sys.stdin:
    if s[0] == "p":
        inorder(node, root)
        print()
        preorder(node, root)
        print()
    else:
        insert(node, int(s[7:]))

import sys


class Node:
    __slots__ = ["key", "left", "right"]

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

    def __str__(self):
        return self.key


root = None


def insert(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        else:
            x = x.right
    if y == None:
        root = Node(z)
    elif z < y.key:
        y.left = Node(z)
    else:
        y.right = Node(z)


def preorder(x):
    return f" {x.key}" + preorder(x.left) + preorder(x.right) if x else ""


def inorder(x):
    return inorder(x.left) + f" {x.key}" + inorder(x.right) if x else ""


eval(input())
node = {}
for s in sys.stdin:
    if s[0] == "p":
        pass
        print((inorder(root)))
        print((preorder(root)))
    else:
        insert(int(s[7:]))

-    def __init__(self, parent=-1, left=-1, right=-1): -        self.parent = parent -        self.left = left -        self.right = right +    __slots__ = ["key", "left", "right"] -    def __eq__(self, other): -        if self.num == other.num: -            return True -        else: -            return False +    def __init__(self, key): +        self.key = key +        self.left, self.right = None, None + +    def __str__(self): +        return self.key -def insert(node, z): -    global root -    p = -1 -    x = root -    while x != -1: -        p = x -        if z < x: -            x = node[x].left -        else: -            x = node[x].right -    if p == -1: -        root = z -        node[z] = Node() -    elif z < p: -        node[p].left = z -        node[z] = Node(p) -    else: -        node[p].right = z -        node[z] = Node(p) +root = None -def preorder(node, i): -    print(" " + str(i), end="") -    if node[i].left != -1: -        preorder(node, node[i].left) -    if node[i].right != -1: -        preorder(node, node[i].right) +def insert(z): +    global root +    x, y = root, None +    while x: +        y = x +        if z < x.key: +            x = x.left +        else: +            x = x.right +    if y == None: +        root = Node(z) +    elif z < y.key: +        y.left = Node(z) +    else: +        y.right = Node(z) -def inorder(node, i): -    if node[i].left != -1: -        inorder(node, node[i].left) -    print(" " + str(i), end="") -    if node[i].right != -1: -        inorder(node, node[i].right) +def preorder(x): +    return f" {x.key}" + preorder(x.left) + preorder(x.right) if x else "" -input() +def inorder(x): +    return inorder(x.left) + f" {x.key}" + inorder(x.right) if x else "" + + +eval(input()) -root = -1 -        inorder(node, root) -        print() -        preorder(node, root) -        print() +        pass +        print((inorder(root))) +        print((preorder(root))) -        insert(node, int(s[7:])) +        insert(int(s[7:]))