First Hellenic Internet Programming Contest
30 November 1996

Problem 3 - String Searching

A binary search tree is used to search for data strings of lowercase 
alphabetic characters (a-z). Each tree node, v, holds a data string, v(s). 
All strings stored in the left subtree of v are lexicographically smaller 
than v(s), whereas all strings in the right subtree of v are 
lexicographically larger than v(s). Also, no string is present in the tree 
more than once. The binary search tree supports insertions and deletions.

Assume that we have a set of strings s1, s2, ..., sn (n<=100), where each 
string comprises of 10 characters at most. The problem is to build a binary 
search tree incrementally, inserting one string at a time. Evidently, the 
tree is not balanced in the general case.

Input
Your program should read the input from the file INPUT3.TXT, which has the 
following format. 
- The first line contains the number of strings, n, to be inserted in the 
binary search tree, whereas 
- the next n lines of the input file contain the strings to be inserted. 

Output
Your program should produce the output in the file OUTPUT3.TXT, which should 
have the following format. 
- The first line contains two integers separated by a space character: the 
maximum path form the root to the leaves, and the internal path length, 
which is equal to the sum of the paths of all the tree nodes (note, that the 
path of the root is zero). These values are indications showing how well the 
tree is balanced. 
- Then, n lines follow, where each line contains one string of characters. 
The characters allowed are "L" (for Left) and "R" (for Right) showing the 
path followed during the insertion of the corresponding string into the tree. 
Two special cases should be taken into consideration:
- If the inserted string is the first in the binary search tree, then the 
string "ROOT" should appear in the corresponding line.
- If the string already exists in the tree, then the string "EXISTS" should 
appear in the output.

Example

Input
7
door
ace
ace
external
extension
cat
flight

Output
2 8
ROOT
L
EXISTS
R
RL
LR
RR