#include<bits/stdc++.h>
using namespace std;
#define int long long
#define aditya ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define endl "\n"
#define pb push_back
#define ss second
#define ff first
#define vi vector<int>
#define all(a) a.begin(),a.end()
#define MAXN 1000001
#define BLOCK 500




struct query{
    int l;
    int r;
    int k;
    int i;
};

deque<int>a(MAXN);
query Q[200001];
int ans[200001];
int fre[1000001];
int cnt = 0;


bool comp(query a , query b){
	if(a.l / BLOCK != b.l/BLOCK)
        return a.l/BLOCK < b.l/BLOCK;

	return a.r < b.r;
}

void add(int pos,int idx){
	int val = a[pos];
	int num = __builtin_popcount(val);
	if(num==Q[idx].k)cnt++;
	fre[cnt]++;
}

void remove(int pos,int idx){
    int val = a[pos];
	int num = __builtin_popcount(val);
	if(num==Q[idx].k)cnt--;
	fre[cnt]--;
}


int32_t main(){
    int t;
    cin>>t;
    while(t--){
        int n,q;
        cin>>n>>q;



        for(int i = 0;i<n;i++){
            cin>>a[i];
        }



        int j = 0;
        while(q--){
            int z;
            cin>>z;

            if(z==1){
                int y;
                cin>>y;
                --y;
                int val = a[y];
//                cout<<"VAL : "<<val<<endl;
                if(val%2==0){
                    auto it = find(a.begin(),a.end(),val);
                    a.push_front(val);
                    a.erase(it);
                }else{
                    auto it = find(a.begin(),a.end(),val);
                    a.push_back(val);
                    a.erase(it);
                }
            }else if(z==2){
                int p,y;
                cin>>y>>p;
                --y;
                a[y] = p;
            }else{
                int l,r,k;
                cin>>l>>r>>k;
                --l;--r;

                Q[j].i = j;
                Q[j].l = l;
                Q[j].r = r;
                Q[j].k = k;
                j++;
            }
//            for(int i = 0;i<n;i++){
//                cout<<a[i]<<" ";
//            }
//            cout<<endl;
        }
        cout<<j<<endl;


        sort(Q , Q+j , comp);

        int ML = 0 , MR = -1;
        for(int i=0;i<j;i++){
            int L = Q[i].l;
            int R = Q[i].r;

            while(ML < L)
                remove(ML,i) , ML++;

            while(ML > L)
                ML-- , add(ML,i);

            while(MR < R)
                MR++ , add(MR,i);

            while(MR > R)
                remove(MR,i) , MR--;

            ans[Q[i].i] = cnt;
        }

        for(int i=0;i<j;i++)
            cout<<ans[i]<<endl;


    }
}