ZADANIE

Rozważmy niepuste drzewo binarne T etykietowane literami alfabetu angielskiego (tylko małe litery) i zapisane wierzchołkowo tak, że pozycję dowolnego wierzchołka x w drzewie T określa ciąg skierowań krawędzi (L - lewa krawędź, R - prawa krawędź) jakie pokonamy przechodząc w tym drzewie ścieżkę od korzenia do wierzchołka x.

Wyznacz najstarsze leksykograficznie słowo, jakie można zbudować z etykiet wierzchołków rozważanego drzewa występujących na dowolnej ścieżce wierzchołek zewnętrzny (liść) drzewa T - korzeń drzewa T.



WEJŚCIE

Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:

 - małą literę alfabetu angielskiego (kod ASCII od 97 do 122) - etykieta wierzchołka,

 - znak odstępu  (kod ASCII 32),

 - ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) - ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.



WYJŚCIE

Wiersz zawierajacy ciąg znaków będący rozwiązaniem postawionego problemu.



OGRANICZENIA

Liczba wierzchołków drzewa T nie większa niż 10^7. Wysokość drzewa T ograniczona przez 2^6.



LIMITY

Złożoność czasowa O(n), złożoność pamięciowa O(n), gdzie n jest liczbą wierzchołków drzewa T.



PRZYKŁAD 1

wejście:

a LL
d
a R
s L

wyjście:

asd

/* KOMENTARZ DO ROZWIĄZANIA




Konstrukcja drzewa binarnego:






    d




   / \




  s   a




 /




a






Możliwe słowa na ścieżce liść drzewa – korzeń drzewa to asd i ad. Leksykograficznie większe jest słowo asd. */



PRZYKŁAD 2

wejście:

s LR
o LRR
m RR
p LRLRL
k
w LRL
a LL
t L
h R
j LRLR

wyjście:

pjwstk



PRZYKŁAD 3

wejście:

w RLR


t LLR


m LLRR


f LRLLL


h LRR


n L


g LLL


v RLL


n RLLR


r RLLRR


k RLRR


k LR


i


f LRLL


z RLLL


y RRLL


i RRLLL


v RRR


z RRRL


n LLLL


w LLRRL


r RR


z R


t RLLLL


w RRLR


s LRL


f RLLRRR


e RRRR


j RLLLR


u RRL


v LL


l RRRLL


p LRLLR


o RL

wyjście:

wurzi



Source code size limit	50000
Available languages	ADA 95 (gnat 4.3.2) Any document (no testing) Assembler (nasm 2.03.01) Bash (bash-4.0.37) Brainf**k (bff 1.0.3.1) C (gcc 4.3.2) C# (gmcs 2.0.1) C++ (g++ 4.3.2) C++ (g++ 4.0.0-8) C99 strict (gcc 4.3.2) Clips (clips 6.24) Clojure (clojure 1.1.0) Common Lisp (clisp 2.44.1) Common Lisp (sbcl 1.0.18) D (gdc 4.1.3) Erlang (erl 5.6.3) F# (fsharp 2.0.0) Fortran 95 (gfortran 4.3.2) Go (gc 2010-07-14) Haskell (ghc 6.10.4) Icon (iconc 9.4.3) Intercal (ick 0.28-4) JAR (JavaSE 6) Java (JavaSE 6) JavaScript (rhino 1.7R1-2) Lua (luac 5.1.3) Nemerle (ncc 0.9.3) Nice (nicec 0.9.6) Ocaml (ocamlopt 3.10.2) Pascal (gpc 20070904) Pascal (fpc 2.2.4) PDF (ghostscript 8.62) Perl (perl 5.12.1) Perl 6 (rakudo-2010.08) PHP (php 5.2.6) Pike (pike 7.6.112) PostScript (ghostscript 8.62) Prolog (swipl 5.6.58) Python (python 2.5) Python 3 (python 3.1.2) Ruby (ruby 1.9.0) Scala (scala 2.8.0) Scheme (stalin 0.11) Scheme (guile 1.8.5) Smalltalk (gst 3.0.3) Tcl (tclsh 8.5.3) TECS Text (plain text) Whitespace (wspace 0.3)