아틴 집합 계산기

문제

Nick은 최근 아틴 집합(artinian set), 줄여서 아틴(artinal)이라 부르는 특별한 종류의 집합을 배웠습니다. 이 집합의 장점은 저마다 유한한 표현을 가진다는 점이어서 컴퓨터로 처리할 수 있습니다. 형식적인 정의는 다소 복잡합니다.

높이가 $\le 0$ 인 아틴은 오직 공집합 ∅ 하나뿐입니다.
양의 정수 $N$ 에 대해, 높이가 $\le N$ 인 아틴은 그 원소가 모두 높이 $\le N-1$ 인 아틴인 유한 집합들과 정확히 일치합니다.
어떤 양의 정수 $N$ 에 대해 $A$ 가 높이 $\le N$ 인 아틴이면, $A$ 를 아틴이라고 합니다.
모든 아틴의 모임을 $U$ 로 씁니다.

높이가 $\le N$ 인 아틴은 높이가 $\le N+1$ 인 아틴이기도 하므로, 임의의 아틴 $A$ 에 대해 높이 $h(A)$ 를 $A$ 가 높이 $\le N$ 인 아틴이 되게 하는 가장 작은 $N$ 으로 정의합니다. 높이가 $N$ 인 아틴을 $N$ -아틴이라고 부릅니다.

여기에 두 가지 개념이 더 필요합니다. $U$ 위의 표준 순서(canonical order, <로 표기)와 아틴의 표준형(canonical form)입니다.

높이가 $\le N$ 인 아틴 $A$ 의 표준형은, 각 $A_i$ 가 높이 $\le N-1$ 인 아틴이고 $A_1 < A_2 < \cdots < A_s$ 를 만족하도록 원소를 나열한 $A = \{A_1, A_2, \ldots, A_s\}$ 입니다.
표준형으로 쓴 두 아틴 $A = \{A_1, \ldots, A_s\}$ 와 $B = \{B_1, \ldots, B_t\}$ 가 모두 높이 $\le N$ 일 때, $A < B$ 인 것은 다음을 만족하는 정수 $k$ ( $1 \le k \le \min(s+1, t)$ )가 존재하는 것과 동치입니다: 모든 $1 \le j < k$ 에 대해 $A_j = B_j$ 이고, $k = s+1$ 이거나 $A_k < B_k$ 이다. 직관적으로는, 정렬된 원소 목록을 왼쪽부터 비교하여 처음으로 다른 원소가 순서를 결정하고, 한쪽이 다른 쪽의 진부분 목록이면 그쪽이 앞섭니다.

아틴의 표준 표현(canonical representation)은 문자 {, }, ,로 이루어진 문자열입니다. repr(∅) = {}이고, $A = \{A_1, \ldots, A_s\}$ 가 표준형이면 repr( $A$ ) = { + repr( $A_1$ ) + , + $\cdots$ + , + repr( $A_s$ ) + }입니다.

표준 표현은 길어지기 쉬우므로 다음 약칭을 도입합니다. 각 정수 $N \ge 0$ 에 대해 유한 서수(finite ordinal) $\mathbf{N}$ 을 귀납적으로 정의합니다: $\mathbf{0} := ∅$ 이고 $\mathbf{N{+}1} := \{\mathbf{N}\} \cup \mathbf{N}$ 이며, 따라서 $\mathbf{N} = \{\mathbf{0}, \mathbf{1}, \ldots, \mathbf{N{-}1}\}$ 입니다. 축약 표준 표현(reduced canonical representation)은 표준 표현에서, 자신보다 큰 서수 $\mathbf{M}$ ( $M > N$ )의 출현 안에 포함되지 않은 모든 서수 $\mathbf{N}$ 의 출현을 십진수 $N$ 으로 바꾼 것입니다.

아틴에 대한 연산은 다음과 같으며, 우선순위가 높은 것부터 낮은 것 순으로 나열합니다.

단항 교집합 ∩: 공집합이 아닌 아틴 $A = \{A_1, \ldots, A_s\}$ 에 대해 ∩ $A := A_1 \cap A_2 \cap \cdots \cap A_s$ .
단항 합집합 ∪: 임의의 아틴 $A = \{A_1, \ldots, A_s\}$ 에 대해 ∪ $A := A_1 \cup A_2 \cup \cdots \cup A_s$ 이고, ∪∅ := ∅.
이항 교집합 ∩: $A \cap B := \{x : x \in A \text{ 이고 } x \in B\}$ .
이항 합집합 ∪: $A \cup B := \{x : x \in A \text{ 또는 } x \in B\}$ .
이항 차집합 −: $A - B := \{x \in A : x \notin B\}$ .
이항 대칭차 △: $A \mathbin{\triangle} B := (A - B) \cup (B - A)$ .

아틴 사이의 관계는 다음과 같이 정의합니다.

상등 =과 부등 ≠.
포함 ⊂과 ⊃: $A ⊂ B \Leftrightarrow B ⊃ A \Leftrightarrow (x \in A \Rightarrow x \in B)$ . 즉 ⊂은 "부분집합 또는 상등"을 뜻합니다.
원소 관계 ∈과 ∋: $B \in A$ (동치로 $A \ni B$ )는 $B$ 가 $A$ 의 원소임을 뜻합니다.
위에서 설명한 표준 순서 관계 <, ≤, ≥, >. 여기서 $A \le B \Leftrightarrow (A < B \text{ 또는 } A = B)$ , $A > B \Leftrightarrow B < A$ , $A \ge B \Leftrightarrow B \le A$ 입니다.

여러분은 아틴으로 계산을 수행하는 작은 프로그램을 실행해야 합니다. 프로그램은 한 줄에 하나씩 놓인 연산자들의 나열입니다. 연산자는 다섯 종류입니다.

대입 ⟨ident⟩:=⟨expr⟩ — 변수 ⟨ident⟩를 ⟨expr⟩의 값으로 설정합니다.
평가 !⟨expr⟩ — ⟨expr⟩를 평가하여 그 축약 표준 표현을 한 줄에 출력합니다.
검사 ?⟨expr⟩⟨relation⟩⟨expr⟩ — 조건을 평가하여 TRUE 또는 FALSE를 한 줄에 출력합니다.
주석 #⟨임의의 문자열⟩ — 그 줄 전체를 출력으로 복사합니다.
빈 연산자 — 공백 문자만으로 이루어진 줄로, 아무 일도 하지 않습니다.

문법에는 다음 정의를 사용합니다.

⟨ident⟩ ::= ⟨alpha⟩{⟨alpha⟩}
⟨alpha⟩ ::= ⟨letter⟩ | ⟨digit⟩ | _
⟨digit⟩ ::= 0 | 1 | … | 9
⟨letter⟩ ::= A | … | Z | a | … | z
⟨expr⟩ ::= { [ ⟨expr⟩ { ,⟨expr⟩ } ] } | ⟨ident⟩ | ⟨expr⟩⟨binop⟩⟨expr⟩ | ⟨unop⟩⟨expr⟩ | (⟨expr⟩)
⟨binop⟩ ::= + | * | - | ^
⟨unop⟩ ::= + | *
⟨relation⟩ ::= < | > | = | <= | >= | <> | -> | <- | << | >>

이항 연산자 +, *, -, ^는 각각 ∪, ∩, −, △을 나타내고, 단항 연산자 +, *는 각각 ∪, ∩을 나타냅니다. 관계 <, >, =, <=, >=, <>, ->, <-, <<, >>는 각각 <, >, =, ≤, ≥, ≠, ∈, ∋, ⊂, ⊃을 나타냅니다. 괄호 (와 )는 통상적으로 우선순위를 바꿉니다. 하나의 ⟨ident⟩를 이루는 ⟨alpha⟩ 문자들만 예외로 하고, 임의의 두 토큰은 임의 개수의 공백 문자(스페이스와 탭)로 구분할 수 있습니다.

프로그램 실행 전에, 이름이 음이 아닌 정수 $N$ 의 (앞자리 0 없는) 십진 표기인 모든 변수는 유한 서수 $\mathbf{N}$ 으로 미리 설정됩니다. 그 밖의 모든 변수는 ∅으로 시작합니다. 식별자는 대소문자를 구별합니다.

입력

입력은 최대 100줄이며, 각 줄에는 연산자가 하나씩 들어 있습니다. 어떤 줄도 254자를 넘지 않습니다.

출력

위 설명대로 ?, !, # 연산자마다 한 줄씩 출력하십시오. 입력은 실행 중 오류가 발생하지 않음이 보장됩니다(예: 단항 ∩은 결코 공집합에 적용되지 않습니다).