class Node():

    key = 0

    l = None

    r = None

    def __init__(self, key):

        self.key = key

T = [None] * 5000005

def insert(z):

    if z == 0: return

    y = 0

    x = 0

    while x is not None:

        y = x

        x = (T[x].l if T[z].key < T[x].key else T[x].r)

    if T[z].key < T[y].key : T[y].l = z

    else : T[y].r = z

def inorder(x):

    if x == None: return;

    inorder(T[x].l);

    print("", T[x].key, end="")

    inorder(T[x].r);

def preorder(x):

    if x == None: return;

    print("", T[x].key, end="")

    preorder(T[x].l);

    preorder(T[x].r);

n = int(input())

for i in range(n):

    s = input()

    if s == "print":

        inorder(0)

        print()

        preorder(0)

        print()

    else:

        x = int(s.split()[1])

        T[i] = Node(x)

        insert(i)

NIL = None

class Tree:

    def __init__(self, key = None):

        self.key = key

        self.p = NIL

        self.left = NIL

        self.right = NIL

n = int(input())

tree = {"root":NIL}

def insert(T, z):

    y = NIL

    x = T["root"]

    while x != NIL:

        y = x

        if z.key < x.key:

            x = x.left

        else:

            x = x.right

    z.p = y

    if y == NIL:

        T["root"] = z

    elif z.key < y.key:

        y.left = z

    else:

        y.right = z

def preorder_tree_walk(T):

    print(f" {T.key}", end="")

    if T.left != NIL:

        preorder_tree_walk(T.left)

    if T.right != NIL:

        preorder_tree_walk(T.right)

def inorder_tree_walk(T):

    if T.left != NIL:

        inorder_tree_walk(T.left)

    print(f" {T.key}", end="")

    if T.right != NIL:

        inorder_tree_walk(T.right)

for _ in range(n):

    ss = input()

    if ss[0] == "i":

        s, v = ss.split()

        insert(tree, Tree(int(v)))

    else:

        inorder_tree_walk(tree["root"])

        print()

        preorder_tree_walk(tree["root"])

        print()



class Node:
    key = 0
    l = None
    r = None

    def __init__(self, key):
        self.key = key


T = [None] * 5000005


def insert(z):
    if z == 0:
        return
    y = 0
    x = 0
    while x is not None:
        y = x
        x = T[x].l if T[z].key < T[x].key else T[x].r
    if T[z].key < T[y].key:
        T[y].l = z
    else:
        T[y].r = z


def inorder(x):
    if x == None:
        return
    inorder(T[x].l)
    print("", T[x].key, end="")
    inorder(T[x].r)


def preorder(x):
    if x == None:
        return
    print("", T[x].key, end="")
    preorder(T[x].l)
    preorder(T[x].r)


n = int(input())
for i in range(n):
    s = input()
    if s == "print":
        inorder(0)
        print()
        preorder(0)
        print()
    else:
        x = int(s.split()[1])
        T[i] = Node(x)
        insert(i)

NIL = None


class Tree:
    def __init__(self, key=None):
        self.key = key
        self.p = NIL
        self.left = NIL
        self.right = NIL


n = int(input())
tree = {"root": NIL}


def insert(T, z):
    y = NIL
    x = T["root"]
    while x != NIL:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == NIL:
        T["root"] = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def preorder_tree_walk(T):
    print(f" {T.key}", end="")
    if T.left != NIL:
        preorder_tree_walk(T.left)
    if T.right != NIL:
        preorder_tree_walk(T.right)


def inorder_tree_walk(T):
    if T.left != NIL:
        inorder_tree_walk(T.left)
    print(f" {T.key}", end="")
    if T.right != NIL:
        inorder_tree_walk(T.right)


for _ in range(n):
    ss = input()
    if ss[0] == "i":
        s, v = ss.split()
        insert(tree, Tree(int(v)))
    else:
        inorder_tree_walk(tree["root"])
        print()
        preorder_tree_walk(tree["root"])
        print()

-class Node: -    key = 0 -    l = None -    r = None - -    def __init__(self, key): -        self.key = key +NIL = None -T = [None] * 5000005 - - -def insert(z): -    if z == 0: -        return -    y = 0 -    x = 0 -    while x is not None: -        y = x -        x = T[x].l if T[z].key < T[x].key else T[x].r -    if T[z].key < T[y].key: -        T[y].l = z -    else: -        T[y].r = z - - -def inorder(x): -    if x == None: -        return -    inorder(T[x].l) -    print("", T[x].key, end="") -    inorder(T[x].r) - - -def preorder(x): -    if x == None: -        return -    print("", T[x].key, end="") -    preorder(T[x].l) -    preorder(T[x].r) +class Tree: +    def __init__(self, key=None): +        self.key = key +        self.p = NIL +        self.left = NIL +        self.right = NIL -for i in range(n): -    s = input() -    if s == "print": -        inorder(0) +tree = {"root": NIL} + + +def insert(T, z): +    y = NIL +    x = T["root"] +    while x != NIL: +        y = x +        if z.key < x.key: +            x = x.left +        else: +            x = x.right +    z.p = y +    if y == NIL: +        T["root"] = z +    elif z.key < y.key: +        y.left = z +    else: +        y.right = z + + +def preorder_tree_walk(T): +    print(f" {T.key}", end="") +    if T.left != NIL: +        preorder_tree_walk(T.left) +    if T.right != NIL: +        preorder_tree_walk(T.right) + + +def inorder_tree_walk(T): +    if T.left != NIL: +        inorder_tree_walk(T.left) +    print(f" {T.key}", end="") +    if T.right != NIL: +        inorder_tree_walk(T.right) + + +for _ in range(n): +    ss = input() +    if ss[0] == "i": +        s, v = ss.split() +        insert(tree, Tree(int(v))) +    else: +        inorder_tree_walk(tree["root"]) -        preorder(0) +        preorder_tree_walk(tree["root"]) -    else: -        x = int(s.split()[1]) -        T[i] = Node(x) -        insert(i)