BST 1

Limit czasu: 1.0s | Limit pamięci: 64MB

Napisz program, który wykonuje następujące operacje na drzewie wyszukiwania binarnego $T$.

• insert $k$: Wstaw węzeł zawierający $k$ jako klucz do $T$.
• print: Wydrukuj klucze drzewa $T$ w porządku INORDER oraz w porządku PREORDER.

Drzewo $T$ jest puste w stanie początkowym.

Wstawianie węzłów do drzewa ma się odbywać zgodnie z poniższym algorytmem:

// Cormen et al. - Introduction to Algorithms
TREE-INSERT(T, z)
   y = NIL
   x = root[T]
   while x != NIL
      y = x
      if key[z] < key[x]
         x = left[x]
      else
         x = right[x]
   parent[z] = y
   if y == NIL
      root[T] = z
   else if key[z] < key[y]
      left[y] = z
   else
      right[y] = z	

Wejście

W pierwszym wierszu podano liczbę operacji $m$. W kolejnych $m$ wierszach podano operacje reprezentowane przez insert $k$ lub print.

Wyjście

Dla każdej operacji print wypisz w jednej linii listę wszystkich kluczy w porządku INORDER, w kolejnej - w porządku PREORDER.

Ograniczenia

• $1 \le m \le 500000$
• liczba operacji print $\leq 10$
• klucze są wartościami typu int
• dane są tak dobrane, że wysokość drzewa nigdy nie przekracza $100$
• wszystkie klucze są różne

Przykłady

Wejście 1

8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print

Wyjście 1

1 12 17 20 25 30 88
30 12 1 20 17 25 88