1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 #define MAXN 100005 6 #define MOD 1000000007 7 int que[MAXN], front = 0, rear = 0; 8 int n; 9 10 void query(int index) {11     int r = rear;12     int square = 0;13     int half = (n+1)>>1;14 15     while (r-- > front) {16         if (que[r] == 3) {17             ++square;18         } else if (que[r] == 2) {19             index = n+1-index;20         } else {21             if (index > half) {22                 index = (index - half)*2;23             } else {24                 index = 2*index - 1;25             }26         }27     }28     __int64 ret = index%MOD;29     for (int i=0; i<square; ++i) {30         ret = ret*ret%MOD;31     }32     printf("%I64d\n", ret);33 }34 35 int main() {36     int t, m;37     int x;38     char cmd[3];39 40     scanf("%d", &t);41     while (t--) {42         rear = 0;43         scanf("%d%d", &n, &m);44         while (m--) {45             scanf("%s %d", cmd, &x);46             if (cmd[0] == ‘Q‘) {47                 query(x);48             } else {49                 que[rear++] = x;50             }51         }52     }53     return 0;54 }