题目描述

Nick 最近学习了一类特殊的集合，称为 Artinian 集合，简称 Artinal。这类集合可以用有限形式表示，因此能够由计算机处理。不过，它们的形式化定义略显复杂。

• 高度不超过 $0$ 的 Artinal 只有空集 $\varnothing$。
• 高度不超过 $n$ 的 Artinal，恰好是由若干个高度不超过 $n-1$ 的 Artinal 组成的有限集合，其中 $n\ge 1$。
• 如果某个集合 $A$ 对至少一个整数 $n$ 而言是高度不超过 $n$ 的 Artinal，那么 $A$ 就是一个 Artinal。
• 所有 Artinal 构成的集合记为 $\mathcal U$。

显然，高度不超过 $n$ 的 Artinal 也一定是高度不超过 $n+1$ 的 Artinal。因此，对任意 Artinal $A$，可以定义其高度 $h(A)$：使得 $A$ 的高度不超过 $n$ 的最小整数 $n$。高度为 $n$ 的 Artinal 也称为一个 $n$-Artinal。

下面定义 $\mathcal U$ 上的规范序（记为 $<$）以及 Artinal 的规范形式。

• 高度不超过 $n$ 的 Artinal $A$ 的规范形式，是如下表示：

  $$A=\{A_1,A_2,\ldots,A_s\},$$

  其中每个 $A_i$ 都是高度不超过 $n-1$ 的 Artinal，并且

  $$A_1<A_2<\cdots<A_s.$$

• 设

  $$A=\{A_1,A_2,\ldots,A_s\},\qquad B=\{B_1,B_2,\ldots,B_t\}$$

  都以规范形式写出。定义 $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$。

对任意 Artinal $A$，定义其规范表示 repr(A)。它是一个仅由字符 {、} 和 , 组成的字符串：

• repr(∅) = "{}"；

• 若 $A=\{A_1,A_2,\ldots,A_s\}$ 为规范形式，则

  repr(A) = "{" + repr(A1) + "," + ... + "," + repr(As) + "}"
  

规范表示往往很长，因此还要定义压缩形式。

对任意整数 $n\ge 0$，递归定义有限序数 $\underline n$：

$$\underline 0:=\varnothing,$$ $$\underline{n+1}:=\{\underline n\}\cup \underline n.$$

为了得到一个 Artinal 的压缩规范表示，先写出其规范表示，然后把其中每个有限序数 $\underline n$ 的出现替换为十进制整数 n，但如果该出现包含在某个更大的有限序数 $\underline m$（$m>n$）的出现中，则不单独替换它。

下面定义 Artinal 上的运算。运算优先级从高到低如下。

1. 一元交 $\bigcap$：对于非空 Artinal

   $$A=\{A_1,A_2,\ldots,A_s\},$$

   定义

   $$\bigcap A:=A_1\cap A_2\cap\cdots\cap A_s.$$

2. 一元并 $\bigcup$：对于任意 Artinal

   $$A=\{A_1,A_2,\ldots,A_s\},$$

   定义

   $$\bigcup A:=A_1\cup A_2\cup\cdots\cup A_s,$$

   并规定 $\bigcup\varnothing:=\varnothing$。

3. 二元交：

   $$A\cap B:=\{x:x\in A\land x\in B\}.$$

4. 二元并：

   $$A\cup B:=\{x:x\in A\lor x\in B\}.$$

5. 差集：

   $$A-B:=\{x\in A:x\notin B\}.$$

6. 对称差：

   $$A\triangle B:=(A-B)\cup(B-A).$$

还定义以下关系：

• 相等 $=$ 与不等 $\ne$；
• 包含关系 $\subset$ 与 $\supset$；
• 元素关系 $\in$ 与 $\ni$；
• 规范序关系 $<$、$>$、$\le$、$\ge$。

Nick 希望你编写一个程序，对 Artinal 进行计算。输入程序由若干条语句组成，每条语句占一行。语句共有五种。

1. 赋值语句

   <ident> := <expr>
   

   将变量 <ident> 的值设置为表达式 <expr> 的值。

2. 求值语句

   !<expr>
   

   计算表达式 <expr>，并在单独一行输出其压缩规范表示。

3. 条件判断语句

   ?<expr><relation><expr>
   

   判断条件是否成立，并在单独一行输出 TRUE 或 FALSE。

4. 注释语句

   #<任意字符>
   

   将整行原样复制到输出。

5. 空语句

   仅由空白字符组成的行，不执行任何操作。

使用以下文法：

<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> ::= "<" | ">" | "=" | "<=" | ">=" | "<>"
             | "->" | "<-" | "<<" | ">>"

二元运算符依次对应：

输入符号	含义
+	并集 $\cup$
*	交集 $\cap$
-	差集 $-$
^	对称差 $\triangle$

一元运算符含义如下：

输入符号	含义
+	一元并 $\bigcup$
*	一元交 $\bigcap$

关系运算符依次对应：

输入符号	含义
<	$<$
>	$>$
=	$=$
<=	$\le$
>=	$\ge$
<>	$\ne$
->	$\in$
<-	$\ni$
<<	$\subset$
>>	$\supset$

圆括号可以像通常一样改变运算优先级。

除组成同一个标识符的连续 <alpha> 字符外，输入中的任意记号之间都可以插入任意数量的空格或制表符。

程序开始执行前：

• 对于每个满足 $0\le n\le 2^9$ 的整数 $n$，名称为其无前导零十进制表示的变量，预先被赋值为有限序数 $\underline n$；
• 其他所有变量初始值均为 $\varnothing$；
• 标识符区分大小写。

输入格式

输入不超过 $100$ 行，每行包含一条语句。

每行长度不超过 $254$ 个字符。

输出格式

对于每条 ?、! 和 # 语句，按照题目描述输出一行。

保证程序执行过程中不会发生运行时错误，例如不会对空集执行一元交运算。

样例输入

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

数据范围与限制

• 时间限制：$5\text{ s}$
• 空间限制：$64\text{ MB}$