C0958 [SDOI2008]校门外的区间

内存限制:256 MB 时间限制:1000 ms

题目描述

受校门外的树这道经典问题的启发,A 君根据基本的离散数学的知识,抽象出 $5$ 种运算维护集合 $S$($S$ 初始为空)并最终输出 $S$。现在,请你完成这道校门外的树之难度增强版——校门外的区间。

$5$ 种运算如下:

$\begin{array}{|c|c|} \hline U\ T & S \cup T \\ \hline I\ T & S \cap T \\ \hline D\ T & S - T \\ \hline C\ T & T - S \\ \hline S\ T & S \oplus T \\ \hline\end{array}$

基本集合运算如下:

$\begin{array}{|c|c|} \hline A \cup B & \{x|x\in A\ \text{or}\ x \in B \} \\ \hline A \cap B & \{x|x\in A\ \text{and}\ x \in B \} \\ \hline A - B & \{x|x\in A\ \text{and}\ x \notin B \} \\ \hline A \oplus B & (A-B)\cup(B-A) \\ \hline \end{array}$

输入格式

输入共 $M$ 行。

每行的格式为X T,用一个空格隔开,$X$ 表示运算的种类,$T$ 为一个区间(区间用 $(a,b), (a,b], [a,b), [a,b]$ 表示)。

输出

共一行,即集合 $S$,每个区间后面带一个空格。若 $S$ 为空则输出 "empty set"。

样例

样例输入 1

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

样例输出 1

(2,3)

提示

对于 $100\%$ 的数据,$0≤a≤b≤65535$,$1≤M≤70000$