1 /******************************
  2 code by drizzle
  3 blog: www.cnblogs.com/hsd-/
  4 ^ ^    ^ ^
  5  O      O
  6 ******************************/
  7 #include<bits/stdc++.h>
  8 #include<map>
  9 #include<set>
 10 #include<cmath>
 11 #include<queue>
 12 #include<bitset>
 13 #include<math.h>
 14 #include<vector>
 15 #include<string>
 16 #include<stdio.h>
 17 #include<cstring>
 18 #include<iostream>
 19 #include<algorithm>
 20 #pragma comment(linker, "/STACK:102400000,102400000")
 21 using namespace std;
 22 #define  A first
 23 #define B second
 24 const int mod=1000000007;
 25 const int MOD1=1000000007;
 26 const int MOD2=1000000009;
 27 const double EPS=0.00000001;
 28 //typedef long long ll;
 29 typedef __int64 ll;
 30 const ll MOD=1000000007;
 31 const int INF=1000000010;
 32 const ll MAX=1ll<<55;
 33 const double eps=1e-5;
 34 const double inf=~0u>>1;
 35 const double pi=acos(-1.0);
 36 typedef double db;
 37 typedef unsigned int uint;
 38 typedef unsigned long long ull;
 39 int t;
 40 char str[10];
 41 map<int,int> mp;
 42 int l,r;
 43 int l0,r0;
 44 int exm;
 45 int flag=0;
 46 int n;
 47 set<int>se;
 48 set<int>::iterator it;
 49 int biao=0;
 50 int main()
 51 {
 52     scanf("%d",&t);
 53     {
 54         for(int k=1; k<=t; k++)
 55         {
 56             se.clear();
 57             mp.clear();
 58             biao=0;
 59             scanf("%d",&n);
 60             l=r=0;
 61             printf("Case #%d:\n",k);
 62             for(int i=1; i<=n; i++)
 63             {
 64                 scanf("%s",str);
 65                 if(strcmp(str,"PUSH")==0)
 66                 {
 67                     scanf("%d",&exm);
 68                     if(exm==0)
 69                         se.insert(l);
 70 
 71                     mp[l]=exm;
 72                     if(biao==0)
 73                         l++;
 74                     else
 75                         l--;
 76                 }
 77                 if(strcmp(str,"POP")==0)
 78                 {
 79                     if(biao==0)
 80                         l--;
 81                     else
 82                         l++;
 83                 }
 84                 if(strcmp(str,"REVERSE")==0)
 85                 {
 86                     if(biao==0)
 87                     {
 88                         l--;
 89                         r--;
 90                         swap(l,r);
 91                         biao=1;
 92                     }
 93                     else
 94                     {
 95                         l++;
 96                         r++;
 97                         swap(l,r);
 98                         biao=0;
 99                     }
100                 }
101                 if(strcmp(str,"QUERY")==0)
102                 {
103                     if(l==r)
104                         printf("Invalid.\n");
105                     else
106                     {
107                         if(biao==0)
108                         {
109                             int exm;
110                             int gg=0;
111                             for(it=se.begin(); it!=se.end(); it++)
112                             {
113                                 if(*it>=r)
114                                 {
115                                     exm=*it;
116                                     gg=1;
117                                     break;
118                                 }
119                             }
120                             if(gg==0)
121                             {
122                                 if((l-r)%2==0)
123                                     printf("0\n");
124                                 else
125                                     printf("1\n");
126                             }
127                             else
128                             {
129                                 if(l==r+1)
130                                     printf("%d\n",mp[exm]);
131                                 else
132                                 {
133                                     if(exm==(l-1))
134                                         exm--;
135                                     if((exm-r+1)%2)
136                                         printf("1\n");
137                                     else
138                                         printf("0\n");
139                                 }
140                             }
141                         }
142                         else
143                         {
144                             int exm;
145                             int gg=0;
146                             if(se.size()!=0)
147                             {
148                                 it=--se.end();
149                                 for(;; it--)
150                                 {
151                                     if(*it<=r)
152                                     {
153                                         exm=*it;
154                                         gg=1;
155                                         break;
156                                     }
157                                     if(it==se.begin())
158                                         break;
159                                 }
160                             }
161                             if(gg==0)
162                             {
163                                 if((r-l)%2==0)
164                                     printf("0\n");
165                                 else
166                                     printf("1\n");
167                             }
168                             else
169                             {
170                                 int hhh=1;
171                                 if(l==r-1)
172                                     printf("%d\n",mp[exm]);
173                                 else
174                                 {
175                                     if(exm==(l+1))
176                                         exm++;
177                                     if((r-exm+1)%2)
178                                         printf("1\n");
179                                     else
180                                         printf("0\n");
181                                 }
182                             }
183                         }
184                     }
185                 }
186             }
187         }
188     }
189     return 0;
190 }
191 /*
192 2
193 6
194 PUSH 1
195 PUSH 1
196 PUSH 1
197 PUSH 1
198 REVERSE
199 QUERY
200 5
201 PUSH 1
202 PUSH 1
203 PUSH 1
204 PUSH 1
205 QUERY
206 */