Friends

Interview

Time limit1sMemory limit128 MB

Summary

Evaluate set expressions over uppercase letters using union, intersection, and difference, where * binds tighter than + and - and equal operators left-associate.

Level: Medium5 of 10
Topics: String, Stack, Implementation, Bit manipulation
Solved: No attempts yet

Problem

You are planning a big birthday party with your friends, and while planning you notice that you have to perform many operations on sets of friends.

To invite two groups g1 and g2 together, the resulting party group is g1 + g2, the union of the two groups.
The intersection of two groups is written g1 * g2 and consists of the members that belong to both groups.
To invite a group g1 but exclude every member of another group g2, you write g1 - g2, the set difference.

Intersection (*) has higher precedence than union (+) and set difference (-). All operations are left associative: in A op1 B op2 C, if op1 and op2 have equal precedence you must evaluate A op1 B first.

Input

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

{ and }
the uppercase letters A to Z, each denoting one friend
the operators +, -, and *
( and ) for grouping

A line is never longer than 255 characters.

Output

For each expression, output the resulting set enclosed in curly braces { and }, one per line. Print the elements of each set in alphabetical order.

Examples1

Example 1

Input

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

Expected output

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