Set Equations

Nick studies set theory and defines set equations. Every set variable denotes a subset of a fixed universal set $\Omega$. Four operations are defined on set variables:

• Intersection $\cap$: $A \cap B = \{\, x : x \in A \wedge x \in B \,\}$
• Union $\cup$: $A \cup B = \{\, x : x \in A \vee x \in B \,\}$
• Difference $-$: $A - B = \{\, x : x \in A \wedge x \notin B \,\}$
• Symmetric difference $\triangle$: $A \triangle B = (A - B) \cup (B - A)$

The operations are listed from highest precedence to lowest: intersection, then union, then difference, then symmetric difference. Parentheses change precedence as usual.

Equations are stored as text using the following grammar:

<ws>       -> ( space | tab )*
<char>     -> 'A' | 'B' | ... | 'Z' | 'a' | 'b' | ... | 'z'
<var>      -> <char> <char>*
<expr>     -> <var>
            | <expr> <ws> <operator> <ws> <expr>
            | '(' <ws> <expr> <ws> ')'
<operator> -> '+' | '*' | '-' | '^'
<equation> -> <expr> <ws> '=' <ws> <expr>

The operations $\cup$, $\cap$, $-$, and $\triangle$ are encoded by the tokens +, *, -, and ^ respectively, and the token = denotes set equality.

Values may be assigned to variables with this notation:

<digit>          -> '0' | '1' | ... | '9'
<element>        -> <digit>*
<variable value> -> <var> <ws> '=' <ws> <values>
<values>         -> <element>
                  | <element> <space or tab> <ws> <values>

You only need to solve one restricted class of equations: every variable other than the universal set occurs exactly once in the equation. Given such an equation together with the values of some variables (the universal set is always among them), decide whether subsets of $\Omega$ can be chosen for the remaining undefined variables so that the equation holds, and if so report those subsets.

The first line is the equation to solve; its length is at most $1000$ characters. Every variable other than the universal set occurs exactly once in the equation.

Each remaining line defines the value of one variable. The universal set is written with the literal name Omega, and its definition is always present. Every variable name is at most $10$ characters long. The universal set has at most $500$ elements, and every element is an integer between $0$ and $500$. All subsets are subsets of $\Omega$. The total length of all variable definitions is at most $100\,000$ characters.

Print Solution on the first line if the equation can be satisfied, or No Solution otherwise.

When a solution exists there may be many valid assignments, so output the following canonical one. Each element of $\Omega$ is treated independently. For a fixed element, consider every way of deciding, for each undefined variable, whether that element belongs to it, keep only those that make the equation hold for this element, and among them choose the lexicographically smallest, ordering the undefined variables by their names in ascending ASCII order and treating "not a member" ($0$) as smaller than "member" ($1$).

After the first line, for every undefined variable, in ascending ASCII order of its name, print one line: the variable name, a space, =, and then, in increasing numeric order, a space followed by each element that belongs to that variable. A variable whose set is empty prints only its name, a space, and =.