1 #include <iostream>  2 #include <cstdio>  3 #include <algorithm>  4 #include <cmath>  5 #include <cstring>  6 #include <queue>  7 #include <set>  8 #include <vector>  9 #include <map> 10 #define ll long long 11  12 using namespace std; 13  14 const int N=100007; 15  16 int cnt=1,root=0; 17 int n,q; 18  19 struct tree{ 20     int key,size,fa; 21     bool flag; 22     int son[2]; 23 }t[N*3]; 24  25 inline int newnode(int key,int fa){ 26     int x=cnt++; 27     t[x].key=key; 28     t[x].size=1; 29     t[x].fa=fa; 30     t[x].son[0]=t[x].son[1]=0; 31     return x; 32 } 33  34 inline void pushup(int x){ 35     t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+1; 36 } 37  38 inline void pushdown(int x){ 39     if (t[x].flag){ 40         t[x].flag=false; 41         swap(t[x].son[0],t[x].son[1]); 42         t[t[x].son[0]].flag^=1; 43         t[t[x].son[1]].flag^=1; 44     } 45 } 46  47 inline int bulid(int L,int R,int fa){ 48     if (L>R) return 0; 49     int mid=(L+R)>>1; 50     int x=newnode(mid,fa); 51     t[x].son[0]=bulid(L,mid-1,x); 52     t[x].son[1]=bulid(mid+1,R,x); 53     pushup(x); 54     return x; 55 } 56  57 inline void init(){ 58     root=0; cnt=1; 59     root=bulid(0,n+1,0); 60 } 61  62 inline void rotate(int x,int p){ 63     int y=t[x].fa; 64     pushdown(y); pushdown(x); 65     t[y].son[!p]=t[x].son[p]; 66     t[t[x].son[p]].fa=y; 67     t[x].fa=t[y].fa; 68     if (t[y].fa) 69         t[t[x].fa].son[t[t[x].fa].son[1]==y]=x; 70     t[x].son[p]=y; 71     t[y].fa=x; 72     pushup(y); 73     pushup(x); 74 } 75  76 inline void Splay(int x,int to){ 77     while (t[x].fa!=to){ 78         if (t[t[x].fa].fa==to) 79             rotate(x,t[t[x].fa].son[0]==x); 80         else { 81             int y=t[x].fa, z=t[y].fa; 82             int p=(t[z].son[0]==y); 83             if (t[y].son[p]==x){ 84                 rotate(x,!p); 85                 rotate(x,p); 86             } 87             else { 88                 rotate(y,p); 89                 rotate(x,p); 90             } 91         } 92     } 93     if (to==0) root=x; 94 } 95  96 inline int get_kth(int x,int k){ 97     if (x==0 || k>t[x].size) return 0; 98     while (x){ 99         pushdown(x);100         if (k==t[t[x].son[0]].size+1) break;101         if (k>t[t[x].son[0]].size+1){102             k-=t[t[x].son[0]].size+1;103             x=t[x].son[1];104         }105         else 106             x=t[x].son[0];107     }108 109     return x;110 }111 112 inline void CUT(int L,int R,int c){113     Splay(get_kth(root,L),0);114     Splay(get_kth(root,R+2),root);115     int tmp=t[t[root].son[1]].son[0];116     t[t[root].son[1]].son[0]=0;117     pushup(t[root].son[1]);118     pushup(root);119 120     Splay(get_kth(root,c+1),0);121     Splay(get_kth(root,c+2),root);122     t[tmp].fa=t[root].son[1];123     t[t[root].son[1]].son[0]=tmp;124     pushup(t[root].son[1]);125     pushup(root);126 }127 128 inline void FILP(int L,int R){129     Splay(get_kth(root,L),0);130     Splay(get_kth(root,R+2),root);131     t[t[t[root].son[1]].son[0]].flag^=1;132     pushup(t[root].son[1]);133     pushup(root);134 }135 136 int cou=0;137 inline void output(int x){138     if (x==0) return;139     pushdown(x);140     output(t[x].son[0]);141     if (t[x].key>=1 && t[x].key<=n) {142         cou++;143         printf("%d",t[x].key);144         if (cou<n) printf(" ");145         else puts("");146     }147     output(t[x].son[1]);148 }149 150 char ch[20];151 152 int main(){153     int x,y,z;154     while (scanf("%d%d",&n,&q)!=EOF){155         if (n==-1) break;156         init();157         while (q--){158             scanf("%s",ch);159             if (ch[0]==‘C‘){160                 scanf("%d%d%d",&x,&y,&z);161                 CUT(x,y,z);162             }163             else {164                 scanf("%d%d",&x,&y);165                 FILP(x,y);166             }167         }168         cou=0;169         output(root);170     }171     return 0;172 }