1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #define KT ch[ch[root][1]][0]  6 #define LC ch[x][0]  7 #define RC ch[x][1]  8 #define N 310001  9  10 using namespace std; 11  12 typedef long long LL; 13  14 struct SplayTree{ 15     int root; 16     int fa[N]; 17     int ch[N][2]; 18     int sz[N]; 19     int top1; 20     int top2; 21     int ss[N]; 22     int que[N]; 23  24  25     void rotate(int x,bool f){ 26         int y=fa[x]; 27         int z=fa[y]; 28         pushdown(y); 29         pushdown(x); 30         ch[y][!f]=ch[x][f]; 31         fa[ch[x][f]]=y; 32         fa[x]=z; 33         if (z) { 34             ch[z][ch[z][1]==y] = x; 35         } 36         ch[x][f] = y; 37         fa[y]=x; 38         pushup(y); 39     } 40     void splay(int x, int g) { 41         int y = fa[x]; 42         pushdown(x); 43         while(y!=g){ 44             int z= fa[y]; 45             bool f = (ch[y][0]==x); 46             if(z != g && f == (ch[z][0]==y)){ 47                 rotate(y,f); 48             } 49             rotate(x,f); 50             y=fa[x]; 51         } 52         pushup(x); 53         if(g==0) root = x; 54     } 55     void rotateTo(int k,int g) { 56         int x=root; 57         pushdown(x); 58         while(sz[LC] != k){ 59             if(k<sz[LC]){ 60                 x=LC; 61             }else{ 62                 k -= sz[LC] + 1; 63                 x = RC; 64             } 65             pushdown(x); 66         } 67         splay(x,g); 68     } 69     void build(int l,int r,int f){ 70         if(l>r){ 71             return ; 72         } 73         int x = (l + r) >> 1; 74         LC = (x - 1 >= l)? (x - 1 + l)>> 1 :0; 75         RC = (r >= x + 1)? (x + 1 + r)>> 1 :0; 76         fa[x] = f; 77         build(l,x - 1,x); 78         build(x + 1,r,x); 79         pushup(x); 80     } 81     void erase(int x){ 82         if(x==0) 83             return; 84         int father= fa[x]; 85         int head = 0, tail=0; 86         for(que[tail++] =x ; head < tail; head++){ 87             ss[top2++] = que[head]; 88             if(ch[que[head]][0]){ 89                 que[tail++]=ch[que[head]][0]; 90             } 91             if(ch[que[head]][1]){ 92                 que[tail++] = ch[que[head]][1]; 93             } 94         } 95         ch[father][ch[father][1]==x]=0; 96         pushup(father); 97     } 98     void makeTree(int &x, int l, int r, int f){ 99         if(l > r){100             return;101         }102         int m=(l+r)>>1;103         newNode(x, num[m]);104         makeTree(LC,l,m-1,x);105         makeTree(RC,m+1,r,x);106         fa[x]=f;107         pushup(x);108     }109 110 111     void newNode(int &x,int c){112         if(top2){113             x = ss[--top2];114         } else {115             x = ++top1;116         }117         LC = RC = fa[x] =0;118         sz[x] = 1;119         val[x]=c;120         flip[x]=add[x]=0;121 122     }123     void pushdown(int x){124         if(add[x]){125             add[LC]+=add[x];add[RC]+=add[x];126             val[LC]+=add[x];val[RC]+=add[x];127             add[x]=0;128         }129         if(flip[x]){130             flip[LC]^=1;flip[RC]^=1;131             reverse(LC);reverse(RC);132             flip[x]=0;133         }134     }135     void pushup(int x){136         sz[x]=1+sz[LC]+sz[RC];137     }138     void reverse(int x){139         swap(LC,RC);140     }141     void treaval(int x){142         if (x) {143             pushdown(x);144             treaval(LC);145             printf("@%I64d",val[x]);146             treaval(RC);147         }148     }149     void debug(){150         treaval(root);151         cout<<endl;152     }153     void cutTo(int l,int r,int c){154         rotateTo(l-1,0);155         rotateTo(r+1,root);156         int tmp=KT;157         KT=0;158         pushup(ch[root][1]);159         pushup(root);160 161         rotateTo(c,0);162         rotateTo(c+1,root);163         fa[tmp]=ch[root][1];164         KT=tmp;165         pushup(ch[root][1]);166         pushup(root);167     }168     void gettar(int len){169         int size=sz[root]-2;170         if(pot+len-1>size){171             cutTo(pot,size,0);172             pot=1;173         }174         rotateTo(pot-1,0);175         rotateTo(pot+len,root);176     }177     void Add(int x){178         gettar(k2);179         add[KT]+=x;180         val[KT]+=x;181     }182     void Rever(){183         gettar(k1);184         flip[KT]^=1;185         reverse(KT);186     }187     void Insert(int x){188         rotateTo(pot,0);189         rotateTo(pot+1,root);190         newNode(KT,x);191         fa[KT]=ch[root][1];192         pushup(ch[root][1]);193         pushup(root);194     }195     void Dele(){196         rotateTo(pot-1,0);197         rotateTo(pot+1,root);198         erase(KT);199         pushup(ch[root][1]);200         pushup(root);201 202         int size=sz[root]-2;203 204         if(pot>size)pot=1;205     }206     void Move(int x){207         int size=sz[root]-2;208         if(x==1){209             pot--;210             if(pot==0){211                 pot=size;212             }213         }else{214             pot++;215             if(pot>size){216                 pot=1;217             }218         }219     }220     void Query(){221         rotateTo(pot,0);222         printf("%I64d\n",val[root]);223     }224     void init(int n,int K1,int K2){225         k1=K1,k2=K2;226 227         top1=top2=root=0;228         newNode(root,0);229         newNode(ch[root][1],0);230         fa[ch[root][1]]=root;231 232         for(int i=1;i<=n;i++)scanf("%d",&num[i]);233 234         makeTree(KT,1,n,ch[root][1]);235         pot=1;236         pushup(ch[root][1]);237         pushup(root);238     }239     void solve(int m){240         char op[10];241         int x;242         //debug();243         for(int i=1;i<=m;i++){244             //cout<<sz[root]<<endl;245             scanf("%s",op);246             if(op[0]==‘q‘){247                 Query();248             }else if(op[0]==‘m‘){249                 scanf("%d",&x);250                 Move(x);251             }else if(op[0]==‘i‘){252                 scanf("%d",&x);253                 Insert(x);254             }else if(op[0]==‘r‘){255                 Rever();256             }else if(op[0]==‘a‘){257                 scanf("%d",&x);258                 Add(x);259             }else{260                 Dele();261             }262             //debug();263         }264     }265     int pot;266     int k1,k2;267     LL val[N];268     int flip[N];269     LL add[N];270     int num[N];271 272 }spt;273 int main()274 {   //freopen("out.txt","w",stdout);275     int n,m,k1,k2;276     int cas=1;277     while(scanf("%d%d%d%d",&n,&m,&k1,&k2),278           n||m||k1||k2){279         printf("Case #%d:\n",cas++);280         spt.init(n,k1,k2);281         spt.solve(m);282 283     }284     return 0;285 }