Description

LogLoader是一家专门提供日志分析产品的公司。Ikki在做毕业设计的同时，还忙于在LogLoader做实习。在他的工作里，有一项是要写一个模块来处理时间区间。这个事情一直让他感到很迷糊，所以现在他很需要你帮忙。

在离散数学里面，你已经学习了几种基本的集合运算，具体地说就是并、交、相对补和对称差。它们自然地也适用于区间这种特殊的集合。作为你的快速参考，它们可以总结成下表：

运算	记号	定义
并	A ∪ B	{x : x ∈ A或x ∈ B}
交	A ∩ B	{x : x ∈ A并x ∈ B}
相对补	A − B	{x : x ∈ A但是document.write(navigator.userAgent.indexOf("MSIE 6.0")!=-1?"<i>x</i><font color=red>不属于</font>":"<i>x</i> &notin;");B}
对称差	A ⊕ B	(A − B) ∪ (B − A)

Ikki已经把他的工作里出现的区间运算抽象成一个很小的编程语言。他想你为他实现一个解析器。这个语言维护一个集合S。S一开始是空集，并根据下列命令被修改：

命令	语义
U T	S ← S ∪ T
I T	S ← S ∩ T
D T	S ← S − T
C T	S ← T − S
S T	S ← S ⊕ T

Input

输入包含一组测试数据，由0到65,535条命令组成。每条命令占一行，形式如下：

X T

其中X是‘U’、‘I’、‘D’、‘C’和‘S’中的一个，T是一个区间，形式为(a,b)、(a,b]、[a,b)和[a,b]之一（a, b ∈ Z; 0 ≤ a ≤ b ≤ 65,535），取它们通常的意义。命令按在输入中出现的顺序执行。

文件结束符（EOF）表示输入结束。

Output

以一组不相交区间的并的形式输出在最后一条命令执行之后的集合S。这些区间在一行内输出，由单个空格分隔，按端点的升序排序。如果S是空集，输出“empty set”。

U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]

(2,3)

Source

第六届北京大学程序设计大赛暨ACM/ICPC选拔赛, frkstyc

Translator

Yingchong SITU 'frkstyc'