import sys



class Node:

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

    def __init__(self, key):

        self.key = key

        self.left = self.right = None



class BST:

    __slots__ = ['root']

    def __init__(self):

        self.root = None

    def insert(self, key):

        x, y = self.root, None

        while x != None: x, y = x.left if key < x.key else x.right, x

        if y == None: self.root = Node(key)

        elif key < y.key: y.left = Node(key)

        else: y.right = Node(key)

    def print_tree(self):

        def inorder(node):

            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''

        def preorder(node):

            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

        print((inorder(self.root)))

        print((preorder(self.root)))



tree = BST()

eval(input())

for e in sys.stdin:

    if e[0] == 'i': tree.insert(int(e[7:]))

    else: tree.print_tree()

import sys



class Node:

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

    def __init__(self, key):

        self.key = key

        self.left = self.right = None



root = None



def insert(key):

    global root

    x, y = root, None

    while x is not None: x, y = x.left if key < x.key else x.right, x

    if y is None: root = Node(key)

    elif key < y.key: y.left = Node(key)

    else: y.right = Node(key)



def inorder(node):

    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''

def preorder(node):

    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''



eval(input())

for e in sys.stdin:

    if e[0] == 'i': insert(int(e[7:]))

    else: print((inorder(root))); print((preorder(root)))

import sys


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

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


class BST:
    __slots__ = ["root"]

    def __init__(self):
        self.root = None

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

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

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

        print((inorder(self.root)))
        print((preorder(self.root)))


tree = BST()
eval(input())
for e in sys.stdin:
    if e[0] == "i":
        tree.insert(int(e[7:]))
    else:
        tree.print_tree()

import sys


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

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


root = None


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


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


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


eval(input())
for e in sys.stdin:
    if e[0] == "i":
        insert(int(e[7:]))
    else:
        print((inorder(root)))
        print((preorder(root)))

-class BST: -    __slots__ = ["root"] - -    def __init__(self): -        self.root = None - -    def insert(self, key): -        x, y = self.root, None -        while x != None: -            x, y = x.left if key < x.key else x.right, x -        if y == None: -            self.root = Node(key) -        elif key < y.key: -            y.left = Node(key) -        else: -            y.right = Node(key) - -    def print_tree(self): -        def inorder(node): -            return ( -                inorder(node.left) + f" {node.key}" + inorder(node.right) -                if node -                else "" -            ) - -        def preorder(node): -            return ( -                f" {node.key}" + preorder(node.left) + preorder(node.right) -                if node -                else "" -            ) - -        print((inorder(self.root))) -        print((preorder(self.root))) +root = None -tree = BST() +def insert(key): +    global root +    x, y = root, None +    while x is not None: +        x, y = x.left if key < x.key else x.right, x +    if y is None: +        root = Node(key) +    elif key < y.key: +        y.left = Node(key) +    else: +        y.right = Node(key) + + +def inorder(node): +    return inorder(node.left) + f" {node.key}" + inorder(node.right) if node else "" + + +def preorder(node): +    return f" {node.key}" + preorder(node.left) + preorder(node.right) if node else "" + + -        tree.insert(int(e[7:])) +        insert(int(e[7:])) -        tree.print_tree() +        print((inorder(root))) +        print((preorder(root)))