[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


题目来源

线段树