Artinals

Nick has been learning about a special kind of set called artinian sets, or artinals for short. Their advantage is that each one has a finite representation, so a computer can process it. The formal definition is a little involved:

• The only artinal of height $\le 0$ is the empty set ∅.
• For a positive integer $N$, the artinals of height $\le N$ are exactly the finite sets whose members are all artinals of height $\le N-1$.
• $A$ is an artinal if it is an artinal of height $\le N$ for some positive integer $N$.
• The collection of all artinals is written $U$.

Every artinal of height $\le N$ is also an artinal of height $\le N+1$, so for any artinal $A$ we define its height $h(A)$ as the smallest $N$ for which $A$ is an artinal of height $\le N$. An artinal of height $N$ is called an $N$-artinal.

Two further notions are needed: the canonical order on $U$ (written <) and the canonical form of an artinal.

• The canonical form of an artinal $A$ of height $\le N$ is the listing $A = \{A_1, A_2, \ldots, A_s\}$ in which every $A_i$ is an artinal of height $\le N-1$ and $A_1 < A_2 < \cdots < A_s$.
• If $A = \{A_1, \ldots, A_s\}$ and $B = \{B_1, \ldots, B_t\}$ are two artinals of height $\le N$ in canonical form, then $A < B$ holds iff there is an integer $k$ with $1 \le k \le \min(s+1, t)$ such that $A_j = B_j$ for every $1 \le j < k$ and either $k = s+1$ or $A_k < B_k$. Intuitively, compare the sorted member lists left to right; the first differing member decides, and a proper prefix ranks first.

The canonical representation of an artinal is a string over the characters {, } and ,: repr(∅) = {}, and if $A = \{A_1, \ldots, A_s\}$ in canonical form, then repr($A$) = { + repr($A_1$) + , + $\cdots$ + , + repr($A_s$) + }.

Canonical representations become long, so a shorthand is introduced. For each integer $N \ge 0$ the finite ordinal $\mathbf{N}$ is defined by induction: $\mathbf{0} := ∅$ and $\mathbf{N{+}1} := \{\mathbf{N}\} \cup \mathbf{N}$, so that $\mathbf{N} = \{\mathbf{0}, \mathbf{1}, \ldots, \mathbf{N{-}1}\}$. The reduced canonical representation is obtained from the canonical representation by replacing, with the decimal numeral $N$, every occurrence of the ordinal $\mathbf{N}$ that is not contained inside an occurrence of some larger ordinal $\mathbf{M}$ (with $M > N$).

The following operations on artinals are defined, from highest priority to lowest:

• Unary intersection ∩: for a non-empty artinal $A = \{A_1, \ldots, A_s\}$, ∩$A := A_1 \cap A_2 \cap \cdots \cap A_s$.
• Unary union ∪: for any artinal $A = \{A_1, \ldots, A_s\}$, ∪$A := A_1 \cup A_2 \cup \cdots \cup A_s$; and ∪∅ := ∅.
• Binary intersection ∩: $A \cap B := \{x : x \in A \text{ and } x \in B\}$.
• Binary union ∪: $A \cup B := \{x : x \in A \text{ or } x \in B\}$.
• Binary difference −: $A - B := \{x \in A : x \notin B\}$.
• Binary symmetric difference △: $A \mathbin{\triangle} B := (A - B) \cup (B - A)$.

The following relations between artinals are defined:

• Equality = and inequality ≠.
• Inclusion ⊂ and ⊃: $A ⊂ B \Leftrightarrow B ⊃ A \Leftrightarrow (x \in A \Rightarrow x \in B)$; that is, ⊂ means "subset or equal".
• Membership ∈ and ∋: $B \in A$ (equivalently $A \ni B$) means $B$ is a member of $A$.
• The canonical-order relations <, ≤, ≥, > described above, where $A \le B \Leftrightarrow (A < B \text{ or } A = B)$, $A > B \Leftrightarrow B < A$, and $A \ge B \Leftrightarrow B \le A$.

You must run a small program that computes with artinals. The program is a sequence of operators, one per line. There are five kinds:

• Assignment ⟨ident⟩:=⟨expr⟩ — sets the variable ⟨ident⟩ to the value of ⟨expr⟩.
• Evaluate !⟨expr⟩ — evaluates ⟨expr⟩ and prints its reduced canonical representation on its own line.
• Check ?⟨expr⟩⟨relation⟩⟨expr⟩ — evaluates the condition and prints TRUE or FALSE on its own line.
• Comment #⟨any characters⟩ — the whole line is copied to the output.
• Empty — a line consisting only of blank characters; it does nothing.

The grammar uses these definitions:

• ⟨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⟩ ::= < | > | = | <= | >= | <> | -> | <- | << | >>

The binary operators +, *, -, ^ denote ∪, ∩, −, △ respectively; the unary operators +, * denote ∪ and ∩. The relations <, >, =, <=, >=, <>, ->, <-, <<, >> denote <, >, =, ≤, ≥, ≠, ∈, ∋, ⊂, ⊃ respectively. Parentheses ( and ) change precedence as usual. Any two tokens — except the ⟨alpha⟩ characters that make up a single ⟨ident⟩ — may be separated by any number of blank characters (spaces and tabs).

Before the program runs, every variable whose name is the decimal representation (without leading zeros) of a non-negative integer $N$ is preset to the finite ordinal $\mathbf{N}$. Every other variable starts as ∅. Identifiers are case-sensitive.

The input consists of at most one hundred lines, each holding a single operator. No line is longer than 254 characters.

Produce one line of output for every ?, ! and # operator, as described above. The input is guaranteed to cause no run-time errors (for example, unary ∩ is never applied to the empty set).