1999/2000 ACM International Collegiate Programming Contest
University of Ulm Local Contest

# Problem F: Friends

Source file: friends.(c|C|pas|java)
Input file: friends.in

You want to plan a big birthday party with your friends. On planning you notice that you have to do a lot of operations with sets of friends. There is one group which consist of Arthur, Biene and Clemens. Then there is a group of friends you know from snowboarding which consists of Daniel, Ernst, Frida and Gustav. If you want to invite them both, the resulting party group consists of g1 + g2 (the result is the union of both groups). Then you can compute the intersection of the two groups g1 * g2, which consists of the empty set. Maybe you want to invite a group g1, but excluding all members of an other group g2, which is written as g1 - g2.
Intersection (*) has precedence over union (+) and set difference (-). All operations are left associative, which means that in A op1 B op2 C you first have to evaluate A op1 B (provided op1 and op2 have equal precedence).

### Input Specification

The input consists of one or more lines. Each line contains one expression that you have to evaluate. Expressions are syntactically correct and only consist of the characters:

- '{' and '}'
- the elements 'A' to 'Z' meaning friend Arthur to Zora.
- the operations '+', '-' and '*'
- '(' and ')' for grouping operations
- the newline character '\n' marking the end of an expression.

A line is never longer than 255 characters.

### Output Specification

Output the resulting set in curly braces '{' and '}', each on a line of its own. Print elements of sets sorted alphabetically.

### Sample Input

    {ABC}
    {ABC}+{DEFG}+{Z}+{}
    {ABE}*{ABCD}
    {ABCD}-{CZ}
    {ABC}+{CDE}*{CEZ}
    ({ABC}+{CDE})*{CEZ}

### Sample Output

    {ABC}
    {ABCDEFGZ}
    {AB}
    {ABD}
    {ABCE}
    {CE}