Description

Nick has recently learned about a special kind of sets called artinian sets or simply artinals. These sets have the advantage of possessing a finite representation, so they can be processed by a computer. However, their formal definition is a bit complicated. Here it is:

• The only artinal of height ≤ 0 is the empty set ∅.
• Artinals of height ≤ n are exactly the finite sets composed of artinals of height ≤ n − 1. Here n ≥ 1 is an arbitrary natural number.
• Finally, A is an artinal if A is an artinal of height ≤ n for at least one integer n.
• The set of all artinals is denoted by U.

It is immediate from the definition that an artinal of height ≤ n is also an artinal of height ≤ n + 1. Thus for any artinal A we can define its height h(A) as the minimal integer n such that A is an artinal of height ≤ n. An artinal of height n is also called an n-artinal. There were two other definitions which took a lot of time to understand. They are the definition of canonical order on U (denoted by <) and the definition of canonical form of an artinal:

• The canonical form of an artinal A of height ≤ n is a representation A = {A₁, A₂, …, A_s} where A_i are artinals of height ≤ n − 1 and A₁ < A₂ < … < A_s.
• If A = { A₁, A₂, …, A_s} and B = { B₁, B₂ , …, B_t} are two artinals of height ≤ n written in the canonical form, then we put A < B iff there exists an integer k, 1 ≤ k ≤ min(s + 1, t), such that A_j = B_j for all integer j such that 1 ≤ j < k and either k = s + 1 or A_k < B_k.

Now we can define for any artinal A its canonical representation. It is a string repr(A) composed of characters ‘{’, ‘}’ and ‘,’ defined in the following way: repr(∅) = “{}”, and if A is an artinal with canonical form A = {A₁, A₂, …, A_s}, then repr(A) = “{” + repr(A₁) + “,” + … + “,” + repr(A_s) + “}”. The canonical representation is often rather lengthy. In order to shorten it, the following definition is introduced. For any integer n ≥ 0 an artinal n (called finite ordinal) is defined by induction on n: 0 := ∅ and n + 1 := {n} ∪ n for all n ≥ 0. Then we can define the reduced canonical representation of an artinal in the following way: We take the canonical representation of this artinal and substitute n for any occurrence of the ordinal n that is not contained in an occurrence of m for some m > n.

Then some operations on artinals are defined. These operations (from highest priority to lowest) are:

• Unary intersection ∩ : for a non-empty artinal A = {A₁, A₂, …, A_s} put ∩A := A₁ ∩ A₂ ∩ … ∩ A_s.
• Unary union ∪: for any artinal A = {A₁, A₂, …, A_s} put ∪A := A₁ ∪ A₂ ∪ … ∪ A_s; ∪∅ := ∅.
• Binary intersection ∩: A ∩ B := {x : x ∈ A ∧ x ∈ B}.
• Binary union ∪: A ∪ B := {x : x ∈ A ∨ x ∈ B}.
• Binary difference −: A − B := {x ∈ A : x ∉ B}.
• Binary symmetrical difference ⊕: A ⊕ B := (A − B) ∪ (B − A).

Besides, some relations between artinals are defined:

• Equality = and inequality ≠.
• Inclusion ⊂ and ⊃: (A ⊂ B) ⇔ (B ⊃ A) ⇔ (x ∈ A ⇒ x ∈ B).
• Element relations ∈ and ∋: B ∈ A (equivalent to A ∋ B) means that B is an element of A.
• Canonical order relations <, >, ≤, ≥ described above (as usual, A ≤ B ⇔ ((A < B) ∨ (A = B)), A > B ⇔ B < A and A ≥ B ⇔ B ≤ A).

Now Nick wants you to write a program that would make some computations with artinals. This program will consist of several operators, each on a separate line. There are five kinds of operators:

• Assignment operator <ident> “:=” <expr> — sets variable <ident> to the value of expression <expr>.
• Evaluate operator “!”<expr> — evaluates <expr> and prints the result in reduced canonical representation on a separate line of output.
• Check condition operator “?”<expr><relation><expr> — checks the condition and outputs either “FALSE” or “TRUE” on a separate line of output.
• Comment operator “#”<any_characters> — the entire line is copied to the output.
• Empty operator — an empty line (i.e. line consisting only of blank characters) — does nothing.

The following definitions are used:
<ident> ::= <alpha>{<alpha>}
<alpha> ::= <letter>|<digit>|“_”
<digit> ::= “0”|“1”|…|“9”
<letter> ::= “A”|“B”|…|“Z”|“a”|“b”|…|“z”
<expr> ::= “{”[<expr>{“,”<expr>}]“}”|<ident>|<expr><binop><expr>|<unop><expr>|“(”<expr>“)”
<binop> ::= “+”|“*”|“−”|“^”
<unop> ::= “+”|“*”
<relation> ::= “<”|“>”|“=”|“<=”|“>=”|“<>”|“−>”|“<−”|“<<”|“>>”
The binary operators (in the order they were listed in the definition of <binop>) correspond to ∪, ∩, − and ⊕; the unary operators correspond to ∪ and ∩; finally, the relations correspond to <, >, =, ≤, ≥, ≠, ∈, ∋, ⊂, ⊃. Parentheses “(” and “)” are used to change the precedence of operations as usual. All tokens of input (except several <alpha> forming a single <ident>) can be separated by an arbitrary number of blank characters (i.e. spaces and tabulation characters).

Besides, before the execution of the program the variables with names that are decimal representations (without leading zeros) of non-negative integers n ≤ 2⁹ are set to the finite ordinals n. All other variables are initialized with ∅. All identifiers are case-sensitive.

Input

The input file consists of not more than one hundred lines each containing a single operator. No line is longer than 254 characters.

Output

Produce one line of output for each “?”, “!” and “#” operator as described above. It is guaranteed that there will be no “run-time errors” (e.g. unary ∩ will never be applied to an empty set).

  !2    + 2
!2*2
!3-4
 #  More examples!

00 := 5+3
! 3-5
! 00
! (5-3)*(5+3)
? 3>9
A := {2,3,9}
B := {1,7}
! A^ B
! +239
? 2->00
? 2<<00
? A>>B
! {{{},{{}},{}},B,{A},{B},{A,B}}+B

2 
2 
0 
 #  More examples!
0 
5 
{3,4}
FALSE 
{1,2,3,7,9}
238 
TRUE 
TRUE 
FALSE 
{1,2,7,{1,7},{{1,7}},{{1,7},{2,3,9}},{{2,3,9}}}

Source

Northeastern Europe 2003, Northern Subregion