[Sdoi2008]校门外的区间
时间限制：10s 空间限制：128MB
题目描述
受校门外的树这道经典问题的启发，A君根据基本的离散数学的知识，抽象出5种运算维护集合S(S初始为空)并最终输出S。现在，请你完成这道校门外的树之难度增强版——校门外的区间。
5种运算如下：
|
U T
|
S∪T
|
|
I T
|
S∩T
|
|
D T
|
S－T
|
|
C T
|
T－S
|
|
S T
|
S⊕T
|
基本集合运算如下：
|
A∪B
|
{x : xÎA or xÎB}
|
|
A∩B
|
{x : xÎA and xÎB}
|
|
A－B
|
{x : xÎA and xÏB}
|
|
A⊕B
|
(A－B)∪(B－A)
|
输入格式
输入共M行。
每行的格式为X T，用一个空格隔开，X表示运算的种类，T为一个区间(区间用(a,b), (a,b], [a,b), [a,b]表示)。
输出格式
共一行，即集合S，每个区间后面带一个空格。若S为空则输出"empty set"。
样例输入
U [1,5] D [3,3] S [2,4] C (1,5) I (2,3]
样例输出
(2,3)
提示
对于 100% 的数据，0≤a≤b≤65535，1≤M≤70000
题目来源
线段树