Programming Problem #27
"Stack Anagrams"

Two words are anagrams if they contain exactly the same letters but in a different order. For example, POLO and LOOP are anagrams. It is sometimes possible to transform a word into one of its anagrams using a stack. We can represent the sequence of stack operations as a string of i and o operations, where i removes the next letter from the input word and pushes it on the stack, and o pops the top letter off the stack and appends it to the output word. The stack and output are initially empty.

The sequences iiioiooo and iiiooioo will both transform POLO into LOOP; the first of these transformations is shown below: 

Operation   Input       Output      Stack (top->)
---------   ---------   ---------   -------------
            POLO
i           OLO                     P
i           LO                      PO
i           O                       POL
o           O           L           PO
i                                   POO
o                       LO          PO
o                       LOO         P
o                       LOOP
The input consists of one or more lines, each of which contains two words separated by a space. The words will consist only of uppercase letters. For each pair of words, output all sequences that will transform the first word into the second, in alphabetical order, as shown in the examples. It is possible that no sequence will work, and if so none should be output.

Input must be read from the file "prob27.in", and output must be written to the file "prob27.out". All output to the screen will be ignored.

Example Input

<BOF>
VEERS SEVER
SHOE HOSE
COW QUASIDEMISEMIHEMISPHERICAL
FREE REEF
<EOF>

Example Output

VEERS -> SEVER
SHOE -> HOSE
iioiooio
COW -> QUASIDEMISEMIHEMISPHERICAL
FREE -> REEF
iioiiooo
iioioioo
A version of this problem originally appeared in the 1991 East Central regionals.

Dr. Eric Shade