> #include<stdio.h>
> #include<string.h>
> #define INT_MAX 2147483647
> const int N = 65535 * 2;
> const int maxn = N * 4;
> 
> int len;
> char s[2],str[20],ch1,ch2;
> int c,d;
> 
> 
> //ans
> char LEFT;
> char RIGHT;
> int LX[N * 10];
> int RY[N * 10];
> int cnt;
> //
> /////////////////////
> struct node
> {
> 	int a,b;
> 	char cov; // 0 ,1 but  -1:mix     
> };
> 
> node tree[maxn];
> 
> void maketree(int a,int b,int k)
> {
> 	tree[k].a = a;
> 	tree[k].b = b;
> 	tree[k].cov = 0;
> 
> 	if(a == b)
> 		return;
> 
> 	int mid = (a+b)>>1;
> 	maketree(a,mid,k<<1);
> 	maketree(mid+1,b,k<<1|1);
> }
> 
> 
> inline void push_down(int k)
> {
> 	tree[k<<1].cov = tree[k].cov;
> 	tree[k<<1|1].cov = tree[k].cov;
> 	tree[k].cov = -1;
> }
> 
> inline void update_info(int k)   //自底向上,更新父结点的cov值
> {
> 	if(tree[k<<1].cov == tree[k<<1|1].cov)  //颜色相同,合并线段
> 		tree[k].cov = tree[k<<1].cov;
> 	else
> 		tree[k].cov = -1;
> }
> 
> ////////////////////
> void insert(int c,int d,int k)    //插入线段c--d
> {
> 	if(tree[k].cov == 1)   //线段已是纯色了,不用再次插入
> 		return;
> 
> 	//cov == 0 或 -1
> 	if(c <= tree[k].a && tree[k].b <= d)   //完全覆盖,则直接改写cov值
> 	{
> 		tree[k].cov = 1;
> 		return;
> 	}
> 
> 	if(tree[k].cov == 0)
> 		push_down(k);
> 	
> 	if(c <= tree[k<<1].b)
> 		insert(c,d,k<<1);
> 
> 	if(d >= tree[k<<1|1].a)
> 		insert(c,d,k<<1|1);
> 
> 	update_info(k);   //自底向上,更新父结点的cov值
> }
> 
> 
> ////////////////////////////
> void del(int c,int d,int k)    //删除线段c--d
> {
> 	if(tree[k].cov == 0)   //线段是空的,不用再次删除
> 		return;
> 
> 	//cov == 1 或 -1
> 	if(c <= tree[k].a && tree[k].b <= d)  //完全覆盖,则直接删除
> 	{
> 		tree[k].cov = 0;
> 		return;
> 	}
> 
> 	if(tree[k].cov == 1)
> 		push_down(k);
> 	
> 	if(c <= tree[k<<1].b)
> 		del(c,d,k<<1);
> 
> 	if(d >= tree[k<<1|1].a)
> 		del(c,d,k<<1|1);
> 
> 	update_info(k);   //自底向上,更新父结点的cov值
> }
> 
> 
> /////////////////////////////////////////
> void insert_xor(int c,int d,int k)    //异或地插入线段[c,d]: 遇到空的线段,直接插入..遇到纯色的线段,删除纯色...
> {
> 	if(tree[k].cov == 1)   //遇到纯色的线段,删除纯色.
> 	{
> 		tree[k].cov = 0;
> 		return;
> 	}
> 
> 	//cov == 0 或 -1
> 	if(c <= tree[k].a && tree[k].b <= d && tree[k].cov == 0)  //遇到空的线段,直接插入
> 	{
> 		tree[k].cov = 1;
> 		return;
> 	}
> 
> 	if(tree[k].cov == 0)
> 		push_down(k);
> 	
> 	if(c <= tree[k<<1].b)
> 		insert_xor(c,d,k<<1);
> 
> 	if(d >= tree[k<<1|1].a)
> 		insert_xor(c,d,k<<1|1);
> 
> 	update_info(k);   //自底向上,更新父结点的cov值
> }
> 
> 
> //////////////////////////////////////////////////
> void insert_sym(int c,int d,int k)    // //加入区域c,d..遇到相交的部分就去除.保留不相交部分.xor异或,很方便
> {
> 
> 	if(c <= tree[k].a && tree[k].b <= d && tree[k].cov >= 0)  //完全覆盖的话,xor一下..
> 	{
> 		tree[k].cov ^= 1;
> 		return;
> 	}
> 
> 	if(tree[k].cov >= 0)
> 		push_down(k);
> 	
> 	if(c <= tree[k<<1].b)
> 		insert_sym(c,d,k<<1);
> 
> 	if(d >= tree[k<<1|1].a)
> 		insert_sym(c,d,k<<1|1);
> 
> 	update_info(k);   //自底向上,更新父结点的cov值
> }
> ////////////////
> 
> 
> 
> 
> inline int str_int(char *str,int i,int j)
> {
> 	int x = 0;
> 	for(int k = i; k<= j; k++)
> 	{
> 		x *= 10;
> 		x += str[k] - 48;
> 	}
> 	return x;
> }
> inline bool pre()
> {
> 	len = strlen(str);
> 	ch1 = str[0];
> 	ch2 = str[len-1];
> 
> 	int mid = 2;
> 
> 	while(str[mid] != ',') mid++;
> 
> 	c = str_int(str,1,mid-1);
> 	
> 	d = str_int(str,mid+1,len-2);
> 
> 	if(c > d)   //空集
> 		return false;
> 
> 	if((c==d) && (ch1 == '(' || ch2 == ')')) //空集
> 		return false;
> 
> 	if(ch1 == '[')
> 		c *= 2;
> 	else
> 		c = c*2 + 1;
> 
> 	if(ch2 == ']')
> 		d *= 2;
> 	else
> 		d = d*2 - 1;
> 
> 	return true;
> }
> 
> 
> /////////////////////////
> int x = -INT_MAX,y = -INT_MAX;
> 
> 
> void Query(int k)    //O(N)
> {
> 	if(tree[k].cov == 0)
> 		return;
> 
> 	if(tree[k].cov == 1)
> 	{
> 		if(y + 1 == tree[k].a) //如果区间可合并,则合并
> 			y = tree[k].b;
> 		else
> 		{
> 			cnt++;
> 			LX[cnt] = x;
> 			RY[cnt] = y;
> 
> 			x = tree[k].a;
> 			y = tree[k].b;
> 		}
> 
> 		return;
> 	}
> 
> 	//cov == -1
> 	Query(k<<1);
> 	Query(k<<1|1);
> }
> 
> ///////////
> 
> int main()
> {
> 	maketree(0,N,1);
> 
> 	while(scanf("%s%s",s,str)!=EOF)
> 	{
> 
> 		if(pre())
> 		{
> 			switch(s[0])
> 			{
> 			case 'U':      //并
> 				insert(c,d,1);
> 				break;
> 		
> 			case 'I':      //交
> 				del(0,c-1,1);
> 				del(d+1,N,1);  //交运算,实质是对原线段删除c,d以外的区域,注意不用再插入线段[c,d]
> 				break;
> 		
> 			case 'D':       //差
> 				del(c,d,1);   //实质是在原有的线段a---b 上删除c--d
> 				break;
> 		
> 			case 'C':       //逆差,实质是对原线段删除c,d以外的区域,然后再xor异或地插入线段[c,d]
> 				del(0,c-1,1); //
> 				del(d+1,N,1);  // //除去c,d以外的区域
> 
> 				insert_xor(c,d,1);   //异或地插入线段[c,d]: 遇到空的线段,直接插入..遇到纯色的线段,删除纯色...
> 				break;
> 		
> 			case 'S':       //对称差
> 				insert_sym(c,d,1);   //加入区域c,d..遇到相交的部分就去除.保留不相交部分.xor异或,很方便
> 			}
> 		}
> 		else //空集
> 		{
> 			switch(s[0])
> 			{
> 			case 'U':      //并   并空集 == 原集
> 				break;
> 		
> 			case 'I':      //交
> 				tree[1].cov = 0; //S 交 空集 == 空集
> 				break;
> 		
> 			case 'D':       //差  差空集 == 原集
> 				break;
> 		
> 			case 'C':       //逆差, 逆差空集 == 空集
> 				tree[1].cov = 0;
> 				break;
> 		
> 			case 'S':       //对称差 无影响  == 原集
> 				break;
> 			}
> 		}
> 
> 	}
> 
> 	cnt = 0;
> 	Query(1);
> 
> 	//最后一个区间 
> 	cnt++;
> 	LX[cnt] = x;
> 	RY[cnt] = y;
> 	
> 
> 	if(cnt == 1)
> 		printf("empty set\n");
> 	else
> 	for(int i=2; i <= cnt; i++)
> 	{
> 		
> 		printf("%c%d,%d%c", LX[i]&1?'(':'[', LX[i]>>1, (RY[i]+1)>>1, RY[i]&1?')':']');
> 
> 		if(i == cnt) printf("\n");
> 		else
> 			printf(" ");
> 	}
> 
> 	//
> 	return 0;
> }