URI Online Judge | 1201

BST Operations II

By Neilor Tonin, URI Brazil

Timelimit: 1

Marcela are still working in the last program and the teacher asked her to write a new computer program about binary search tree. This new program is similar with the previous one, but it works with integer numbers and must have a new command "R". See the commands:

By using this program, at any time must be possible to insert a new element, print the Pre-order, In-order or Post-order traversal, search any element inside the tree or even remove any element.

Note: If an element with two subtrees (left and right) is removed, the antecessor (the bigger element from left subtree, must occupy its place and in case of attempt of remove an element inexistent none message must be printed.

Input

The input contains N lines and each line contains an operation using integer numbers (1-106) over a binary search tree, that initially will be empty. The first line of input contains an insertion (I). The next lines can have any command described above, like the given example. The end of input is determined by EOF.

Output

Each line of the input excepting the lines with the "I" or the "R" commands must produce one output line. The output must be acording to the given example, remembering that "existe" means exist and "nao existe" means don't exist in portuguese. There is no blank space after the last line char, otherwise you`ll get Presentation Error.

Sample Input Sample Output

I 5
I 2
I 4
I 1
INFIXA
PREFIXA
POSFIXA
P 3
P 1
INFIXA
R 1
INFIXA

1 2 4 5
5 2 1 4
1 4 2 5
3 nao existe
1 existe
1 2 4 5
2 4 5