1 #include<iostream>
  2 #include<cassert>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cstdio>
  6 using namespace std;
  7 const int N = 100005;
  8 int num[N],now;
  9 pair<int,int> hash[N];
 10 int seg[N<<2],M;
 11 // chairman tree
 12 const int MAXN = 2000000;
 13 int sum[MAXN],pl[MAXN],pr[MAXN],size,root[N];
 14 int make_tree(int l, int r, int val){
 15     int t = size++;
 16 //    cout<<l<<" "<<r<<" "<<val<<endl;
 17     if(l == r) { sum[t] = val; return t;}
 18     int m = l+r>>1;
 19     pl[t] = make_tree(l,m,val);
 20     pr[t] = make_tree(m+1,r,val);
 21     sum[t] = sum[pl[t]] + sum[pr[t]];
 22     return t;
 23 }
 24 int make_tree(int l,int r, int _pl,int _pr){
 25     int t = size ++;
 26     pl[t] = _pl; pr[t] =_pr;
 27     sum[t] = sum[_pl] + sum[_pr];    
 28     return t;
 29 }
 30 int change(int L, int R,int pos, int at, int v){
 31     if(L == R)
 32         return make_tree(L,R,v);
 33     int m = L+R >> 1;
 34     if(at <=m ) return make_tree(L,R, change(L,m,pl[pos] , at, v),pr[pos]);
 35     return make_tree(L, R , pl[pos] , change(m+1,R,pr[pos] ,at, v));
 36 }
 37 int ask(int l,int r, int pos, int L, int R){
 38     if(l <= L && r >= R) 
 39         return sum[pos];
 40     int mid = L+R >>1 , val = 0;
 41     if(l <= mid) val += ask(l,r,pl[pos], L, mid);
 42     if(r > mid) val += ask(l,r,pr[pos], mid+1,R);
 43     return val;
 44 }
 45 // init()
 46 int n;
 47 void init(){
 48     size = 0;
 49     for(int i=0;i<n;i++)
 50         hash[i] = make_pair(num[i] , i);
 51     sort(hash, hash + n);
 52     root[0] = make_tree(0,n-1,1);
 53     for(int i=1; i<n; i++){
 54         root[i] = change(0,n-1,root[i-1],hash[i-1].second , -1);
 55     }
 56 //    cout<<size<<endl;
 57     for(int i=30; i>=0; i--) if(n < (1<<i)) M = 1<<i;
 58     for(int i=0; i<M*2; i++) seg[i] = 0;
 59 }
 60 // segment tree
 61 void ins(int pos){
 62     for(pos += M; pos; pos >>= 1)
 63         seg[pos] ++;
 64 }
 65 int find_rank(int pos){
 66     int ans = 0;
 67     for(pos += M; pos; pos >>=1)
 68         if(pos &1) ans += seg[pos ^ 1];
 69     return ans +1;
 70     
 71 }
 72 int find_kth(int k){
 73     int ans=1;
 74     while(ans < M){
 75         int l = ans <<1;
 76         int r = ans <<1|1;
 77         assert(seg[ans] >= k);
 78         if(seg[l] >= k) ans = l;
 79         else {
 80             k -= seg[l];
 81             ans = r;
 82         }
 83     }
 84     return hash[ans-M].first;
 85 }
 86 // main
 87 int find(int val){
 88     int l = 0, r= n;
 89     while(l<r){
 90         int mid = l+r >>1;
 91         if(val <= hash[mid].first) r = mid;
 92         else l = mid+1;
 93     }
 94     return l;
 95 }
 96 int chk(int pos, int l, int r){
 97     int val = ask(l,r,root[pos],0,n-1);
 98     int ans = (r-l+1-val >> 1) + 1;
 99 //    cout<<(ans)<<endl;
100     return ans;
101 }
102 struct Query{
103     char cmd[20];
104     int l,r,v;
105 } query[N*5];
106 int main(){
107     int _test = 0,Q;
108     while(~scanf("%d",&Q)){
109         n = 0;
110         for(int i=0; i<Q;i++){
111             scanf("%s",query[i].cmd);
112             if(!strcmp(query[i].cmd, "Insert")){
113                 scanf("%d",&query[i].v);
114                 num[n++] = query[i].v;
115             }
116             else {
117                 char x = query[i].cmd[strlen(query[i].cmd) -1];
118                 if(x =='1')
119                     scanf("%d%d%d",&query[i].l , &query[i].r ,&query[i].v);
120                 else scanf("%d",&query[i].v);
121             }
122         }
123         init();
124         long long Q1 = 0, Q2= 0, Q3 = 0;
125         printf("Case %d:\n", ++ _test);
126         for(int i=0;i<Q;i++){
127             if(!strcmp(query[i].cmd,"Insert")){
128                 ins(find(query[i].v));
129             }
130             else {
131                 char x = query[i].cmd[strlen(query[i].cmd) -1];
132                 if(x == '1'){
133                     int L = query[i].l-1, R = query[i].r-1 , k = query[i].v;
134                     int l = 0, r = n;
135 //                    cout<<"qeury_1 "<<L<<" "<<R<<" "<<k<<endl;
136                     while(l < r){
137                         int m = l+r >>1;
138 //                        cout<<l<<" "<<r<<" "<<m<<" "<<hash[m].first<<endl;
139                         if(chk(m,L,R) > k) r = m ;
140                         else l = m+1;
141                     }
142                     l--;
143                     int v1 = hash[l].first;
144                     Q1 += v1;
145                     //cout<<v1<<endl;
146                 }
147                 else if(x=='2'){
148                     int u = find(query[i].v);
149                     int v2 = find_rank(u);
150                     //cout<<v2<<endl;
151                     Q2 += v2;
152                 }
153                 else {
154                     int v3 = find_kth(query[i].v);
155                     Q3 += v3;
156                     //cout<<v3<<endl;
157                 }
158             }
159         }
160         cout<<Q1<<endl<<Q2<<endl<<Q3<<endl;
161 //        cout<<size<<endl;
162     }
163 }
164