Search trees are data structures that support dynamic set operations including insert, search, delete and so on. Thus a search tree can be used both as a dictionary and as a priority queue.  Binary search tree is one of fundamental search trees. The keys in a binary search tree are always stored in such a way as to satisfy the following binary search tree property:    * Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $x.key \leq y.key$.   The following figure shows an example of the binary search tree.      For example, keys of nodes which belong to the left sub-tree of the node containing 80 are less than or equal to 80, and keys of nodes which belong to the right sub-tree are more than or equal to 80. The binary search tree property allows us to print out all the keys in the tree in sorted order by an inorder tree walk.  A binary search tree should be implemented in such a way that the binary search tree property continues to hold after modifications by insertions and deletions. A binary search tree can be represented by a linked data structure in which each node is an object. In addition to a key field and satellite data, each node contains fields _left_ , _right_ , and _p_ that point to the nodes corresponding to its left child, its right child, and its parent, respectively.  To insert a new value $v$ into a binary search tree $T$, we can use the procedure insert as shown in the following pseudo code. The insert procedure is passed a node $z$ for which $z.key = v$, $z.left = NIL$, and $z.right = NIL$. The procedure modifies $T$ and some of the fields of $z$ in such a way that $z$ is inserted into an appropriate position in the tree.                 1 insert(T, z) 2     y = NIL // parent of x 3     x = 'the root of T' 4     while x ≠ NIL 5         y = x // set the parent 6         if z.key < x.key 7             x = x.left // move to the left child 8         else  9             x = x.right // move to the right child 10    z.p = y 11 12    if y == NIL // T is empty 13        'the root of T' = z 14    else if z.key < y.key 15        y.left = z // z is the left child of y 16    else  17        y.right = z // z is the right child of y   Write a program which performs the following operations to a binary search tree $T$.    * insert  $k$: Insert a node containing $k$ as key into $T$.   * print: Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.  You should use the above pseudo code to implement the insert operation. $T$ is empty at the initial state.
class Node:
  key = None
  left = None
  right = None
  def __init__(self, k):
    self.key = k

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z
        
  def inorder(self):
    
    res = []
    cur_node = self.root
    right_successor = []
    left_successor = []
    
    if cur_node is None:
      return res
    
    while cur_node is not None:
      res.append(cur_node.key)
      
      if cur_node.left is not None:
        left_successor.append(cur_node.left)
      if cur_node.right is not None:
        right_successor.append(cur_node.right)
      
      cur_node = left_successor.pop() if len(left_successor) > 0 else right_successor.pop() if len(right_successor) else None
    return res
      
n = int(input())
bst = BST()
for _ in range(n):
  query = [int(x) if x.isnumeric() else x for x in input().split()]
  if query[0] == 'insert':
    bst.insert(query[1])
  elif query[0] == 'print':
    ans = bst.inorder()
    print(" " + " ".join(list(map(str, ans))))

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

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z

  def inorder(self, r, lis):
    
    if r != None:
      self.inorder(r.left, lis)
      lis.append(r.key)
      self.inorder(r.right, lis)


  def preorder(self, r, lis):
    
    if r != None:
      lis.append(r.key)
      self.preorder(r.left, lis)
      self.preorder(r.right, lis)

    
n = int(input())
bst = BST()
for _ in range(n):
  # query = [int(x) if re.match('[+|-]?\d', x) else x for x in input().split()]
  query = input().split()
  if query[0] == 'insert':
    bst.insert(int(query[1]))
  elif query[0] == 'print':
    root = bst.root
    in_lis = []
    pre_lis = []
    bst.preorder(root, pre_lis)
    bst.inorder(root, in_lis)
    print(" " + " ".join(list(map(str, in_lis))))
    print(" " + " ".join(list(map(str, pre_lis))))
