output_description: For each print operation, print a list of keys obtained by inorder tree walk
  and preorder tree walk in a line respectively. Put a space character _before
  each key_.
input_description: In the first line, the number of operations $m$ is given. In the following $m$
  lines, operations represented by insert $k$ or print are given.
attempt: m = int(input())
  
  l, r = {}, {}
  
  
  def insertnode(num, x):
      """xには毎回rootを設定（rootから順に比較してし、適した場所に追加）"""
      if num < x:
          if x in l:
              if l[x] != 3000000000:
                  insertnode(num, l[x])
              else:
                  l[x] = num
                  return
          else:
              l[x] = num
              return
      else:
          if x in r:
              if r[x] != 3000000000:
                  insertnode(num, r[x])
              else:
                  r[x] = num
                  return
          else:
              r[x] = num
              return
  
  
  def inorder(num):
      if num == 3000000000:
          return
      if num in l:
          inorder(l[num])
      else:
          l[num] = 3000000000
          inorder(l[num])
      print(" " + str(num), end="")
      if num in r:
          inorder(r[num])
      else:
          r[num] = 3000000000
          inorder(r[num])
  
  
  def preorder(num):
      if num == 3000000000:
          return
      print(" " + str(num), end="")
      if num in l:
          preorder(l[num])
      else:
          l[num] = 3000000000
          preorder(l[num])
      if num in r:
          preorder(r[num])
      else:
          r[num] = 3000000000
          preorder(r[num])
  
  
  for i in range(m):
      order = input()
      if i == 0:
          global root
          root = int(order[7:])
          continue
      if order[0] == "i":
          num = int(order[7:])
          insertnode(num, root)
      else:
          inorder(root)
          print()
          preorder(root)
          print()
  
problem_description: Binary Search Tree I
  
  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.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ALDS1_8_A.png)  
  
  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.
samples: [{"input": "8\n    insert 30\n    insert 88\n    insert 12\n    insert 1\n    insert 20\n    insert 17\n    insert 25\n    print", "output": "1 12 17 20 25 30 88\n     30 12 1 20 17 25 88"}]