집합 방정식

Nick은 집합론을 공부하다가 집합 방정식을 정의했다. 각 집합 변수는 고정된 전체집합 $\Omega$의 부분집합을 나타낸다. 집합 변수에는 다음 네 가지 연산이 정의된다.

• 교집합 $\cap$: $A \cap B = \{\, x : x \in A \wedge x \in B \,\}$
• 합집합 $\cup$: $A \cup B = \{\, x : x \in A \vee x \in B \,\}$
• 차집합 $-$: $A - B = \{\, x : x \in A \wedge x \notin B \,\}$
• 대칭차집합 $\triangle$: $A \triangle B = (A - B) \cup (B - A)$

연산의 우선순위는 높은 것부터 낮은 것 순으로 교집합, 합집합, 차집합, 대칭차집합이다. 괄호는 일반적인 방식대로 우선순위를 바꾼다.

방정식은 다음 문법으로 텍스트로 저장된다.

<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>

연산 $\cup$, $\cap$, $-$, $\triangle$는 각각 토큰 +, *, -, ^로 표기하며, 토큰 =는 집합의 상등을 나타낸다.

변수에는 다음 표기로 값을 지정할 수 있다.

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

당신은 한 가지 제한된 종류의 방정식만 풀면 된다. 전체집합을 제외한 모든 변수는 방정식에 정확히 한 번씩만 나타난다. 이러한 방정식과 일부 변수의 값(전체집합은 항상 주어진다)이 주어질 때, 나머지 미정의(undefined) 변수에 $\Omega$의 부분집합을 지정해 방정식을 성립시킬 수 있는지 판정하고, 가능하다면 그 부분집합들을 출력하라.

첫째 줄에는 풀어야 할 방정식이 주어지며, 길이는 최대 $1000$자이다. 전체집합을 제외한 모든 변수는 방정식에 정확히 한 번 나타난다.

이후 각 줄은 한 변수의 값을 정의한다. 전체집합은 리터럴 이름 Omega로 표기되며 그 정의는 항상 존재한다. 각 변수 이름의 길이는 최대 $10$자이다. 전체집합의 원소 개수는 최대 $500$개이고, 각 원소는 $0$ 이상 $500$ 이하의 정수이다. 모든 집합은 $\Omega$의 부분집합이다. 모든 변수 정의의 총 길이는 최대 $100\,000$자이다.

방정식을 만족시킬 수 있으면 첫째 줄에 Solution을, 그렇지 않으면 No Solution을 출력한다.

해가 존재할 때는 유효한 배정이 여러 개일 수 있으므로 다음의 표준(canonical) 해를 출력한다. $\Omega$의 각 원소를 독립적으로 처리한다. 한 원소를 고정하고, 각 미정의 변수에 대해 그 원소가 그 변수에 속하는지 여부를 정하는 모든 방법 중에서 이 원소에 대해 방정식을 성립시키는 것만 남긴 뒤, 그중 사전순으로 가장 작은 것을 고른다. 이때 미정의 변수는 이름의 오름차순 ASCII 순서로 나열하고, "속하지 않음"($0$)을 "속함"($1$)보다 작은 것으로 본다.

첫째 줄 다음에는 이름의 오름차순 ASCII 순서로 각 미정의 변수에 대해 한 줄씩 출력한다. 각 줄은 변수 이름, 공백, =을 쓰고, 그 뒤에 그 변수에 속하는 원소들을 증가하는 수 순서로 각각 공백에 이어 출력한다. 집합이 비어 있는 변수는 이름, 공백, =만 출력한다.