我们的难点非常明显——怎么对这些数进行操作，因为在我们的感知内，位运算并没有加法结合律。

但是仔细看一下题，发现每一个元素只给了不超过15那么大的，不超过15，如果换成二进制位的话，只有四位，如果位运算一位一位的搞，最后再整合，同时，opn某一位上是0或者1分开来考虑，那么与和或就是覆盖0或者是覆盖1，异或操作就是直接取反，那不就恰好是HDU3397那种单个位上面的操作了吗？我们不必去考虑二进制的进位问题，我们只需要记录下来四位里面每一位有多少个1，那么最终整合的时候就可以得到正确的解

对于与和或操作，它们的优先级大于异或操作，也就是说当一个区间得到了这两个操作的时候，异或操作的标记应该清零。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn = (int)1e6 + 10;
int a[maxn], n, m;
int cnt0[maxn << 2], cnt1[maxn << 2], flag[maxn << 2], flag_x[maxn << 2];
void fun(int iflag, int iflag_x, int l, int r, int rt){
    if (iflag != -1){
        flag[rt] = iflag;
        if (iflag == 0) cnt0[rt] = (r - l + 1), cnt1[rt] = 0;
        else if (iflag == 1) cnt1[rt] = (r - l + 1), cnt0[rt] = 0;
        flag_x[rt] = 0;
    }
    if (iflag_x){
        flag_x[rt] ^= 1;
        swap(cnt0[rt], cnt1[rt]);
    }
}
void PushDown(int l, int r, int rt){
    if (flag[rt] != -1 || flag_x[rt] == 1){
        int m = (l + r) >> 1;
        fun(flag[rt], flag_x[rt], lson);
        fun(flag[rt], flag_x[rt], rson);
        flag[rt] = -1; flag_x[rt] = 0;
    }
}
void PushUp(int rt){
    cnt0[rt] = cnt0[rt << 1] + cnt0[rt << 1 | 1];
    cnt1[rt] = cnt1[rt << 1] + cnt1[rt << 1 | 1];
}
void build(int l, int r, int rt, int bit){
    cnt0[rt] = cnt1[rt] = flag_x[rt] = 0; flag[rt] = -1;
    if (l == r){
        if ((a[l] & (1 << bit)) == 0) cnt0[rt] = 1;
        else cnt1[rt] = 1;
        return;
    }
    int m = (l + r) >> 1;
    build(lson, bit); build(rson, bit);
    PushUp(rt);
}
void update(int ll, int rr, int iflag, int iflag_x, int l, int r, int rt){
    if (ll <= l && rr >= r){
        fun(iflag, iflag_x, l, r, rt);
        return;
    }
    PushDown(l, r, rt);
    int m = (l + r) >> 1;
    if (ll <= m) update(ll, rr, iflag, iflag_x, lson);
    if (rr > m) update(ll, rr, iflag, iflag_x, rson);
    PushUp(rt);
}
int query(int ll, int rr, int l, int r, int rt){
    if (ll <= l && rr >= r) return cnt1[rt];
    PushDown(l, r, rt);
    int m = (l + r) >> 1;
    int num = 0;
    if (ll <= m) num += query(ll, rr, lson);
    if (rr > m) num += query(ll, rr, rson);
    PushUp(rt); return num;
}
struct OP{
    char cmd[10];
    int opn, l, r, cnt[5];
    void get(){
        memset(cnt, 0, sizeof(cnt));
        scanf("%s", cmd);
        if (cmd[0] == 'S') scanf("%d%d", &l, &r);
        else scanf("%d%d%d", &opn, &l, &r);
        l = max(0, l); r = min(n - 1, r);
    }
    void print(){
        for (int i = 0; i < 4; i++) printf("%d ", cnt[i]);
        puts("");
    }
};
OP op[100005];
void work(int bit){
    build(0, n - 1, 1, bit);
    for (int i = 0; i < m; i++){
        if (op[i].cmd[0] == 'A'){
            if (op[i].opn & (1 << bit)) continue;
            else update(op[i].l, op[i].r, 0, 0, 0, n - 1, 1);
        }else if (op[i].cmd[0] == 'O'){
            if (op[i].opn & (1 << bit)) update(op[i].l, op[i].r, 1, 0, 0, n - 1, 1);
            else continue;
        }else if (op[i].cmd[0] == 'X'){
            if (op[i].opn & (1 << bit)) update(op[i].l, op[i].r, -1, 1, 0, n - 1, 1);
            else continue;
        }
        else op[i].cnt[bit] = query(op[i].l, op[i].r, 0, n - 1, 1);
    }
}
void solve(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) op[i].get();
    for (int i = 0; i < 4; i++) work(i);
    for (int i = 0; i < m; i++) if (op[i].cmd[0] == 'S'){
        int ans = op[i].cnt[0] + op[i].cnt[1] * 2 + op[i].cnt[2] * 4 + op[i].cnt[3] * 8;
        printf("%d\n", ans);
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "rt", stdin);
    #endif
    int cs; cin >> cs;
    while(cs--) solve();
    return 0;
}