/*

一开始维护了两个标记 开了两个数组

想的是 可能当前两种操作都要做

但是太复杂了 不好处理

其实 当前要做的标记可以只有一个

我们在Insert的时候 

要打的标记是2即翻转区间: 

1.如果原来是区间赋值1 先赋值1在翻转 问题不大 标记变 1-1=0

2.如果原来是区间赋值0 同上 问题不大 标记 1-0=1

3.如果原始是区间翻转 抵消1-2=-1

4.如果原来是-1 无标记 就打上 1-(-1)=2 这个时候要先把区间的01信息互换 

要打的标记是01即区间赋值

就无视之前的翻转操作 直接打上标记更新k 

然后Up的时候(标记下方)就只有一个标记

1.如果是2 就下放 改了左右儿子 然后同上进行标记改变

2.如果是01

*/

#include<cstdio>

#include<cstring>

#include<iostream>

#define lc k*2

#define rc k*2+1

#define len (r-l+1)

#define mid (l+r)/2

#define maxn 400010

using namespace std;

int T,I,n,m,s1[maxn],s0[maxn],l1[maxn],l0[maxn],r1[maxn],r0[maxn],mx1[maxn],mx0[maxn],a[maxn];

void Swap(int k,int l,int r){

    a[k]=-a[k];swap(s1[k],s0[k]);swap(l1[k],l0[k]);

    swap(r1[k],r0[k]);swap(mx1[k],mx0[k]);

}

void Up(int k,int l,int r){

    if(a[k]==){

        a[k]=-;Swap(lc,l,mid);Swap(rc,mid+,r);return;

    }

    a[lc]=a[rc]=a[k];

    s1[lc]=(mid-l+)*a[k];s0[lc]=(mid-l+)*(a[k]^);

    s1[rc]=(r-mid)*a[k];s0[rc]=(r-mid)*(a[k]^);

    l1[lc]=(mid-l+)*a[k];l0[lc]=(mid-l+)*(a[k]^);

    l1[rc]=(r-mid)*a[k];l0[rc]=(r-mid)*(a[k]^);

    r1[lc]=(mid-l+)*a[k];r0[lc]=(mid-l+)*(a[k]^);

    r1[rc]=(r-mid)*a[k];r0[rc]=(r-mid)*(a[k]^);

    mx1[lc]=(mid-l+)*a[k];mx0[lc]=(mid-l+)*(a[k]^);

    mx1[rc]=(r-mid)*a[k];mx0[rc]=(r-mid)*(a[k]^);

    a[k]=-;

}

void Insert(int k,int l,int r,int x,int y,int z){

    if(x<=l&&y>=r){

        if(z==)Swap(k,l,r);

        else {

            a[k]=z;s1[k]=len*z;s0[k]=len*(z^);mx1[k]=len*z;mx0[k]=len*(z^);

            l1[k]=len*z;l0[k]=len*(z^);r1[k]=len*z;r0[k]=len*(z^);

        }

        return;

    }

    if(a[k]!=-)Up(k,l,r);

    if(x<=mid)Insert(lc,l,mid,x,y,z);

    if(y>mid)Insert(rc,mid+,r,x,y,z);

    s1[k]=s1[lc]+s1[rc];s0[k]=s0[lc]+s0[rc];

    l1[k]=l1[lc]+(l1[lc]==mid-l+)*l1[rc];

    r1[k]=r1[rc]+(r1[rc]==r-mid)*r1[lc];

    l0[k]=l0[lc]+(l0[lc]==mid-l+)*l0[rc];

    r0[k]=r0[rc]+(r0[rc]==r-mid)*r0[lc];

    mx1[k]=max(mx1[lc],max(mx1[rc],r1[lc]+l1[rc]));

    mx0[k]=max(mx0[lc],max(mx0[rc],r0[lc]+l0[rc]));

}

int Query1(int k,int l,int r,int x,int y){

    if(x<=l&&y>=r)return s1[k];

    int res=;

    if(a[k]!=-)Up(k,l,r);

    if(x<=mid)res+=Query1(lc,l,mid,x,y);

    if(y>mid)res+=Query1(rc,mid+,r,x,y);

    return res;

}

int Query2(int k,int l,int r,int x,int y){

    if(x<=l&&y>=r)return mx1[k];

    if(a[k]!=-)Up(k,l,r);

    int res=;

    if(x<=mid)res=max(res,Query2(lc,l,mid,x,y));

    if(y>mid)res=max(res,Query2(rc,mid+,r,x,y));

    if(x<=mid&&y>mid)res=max(res,min(mid-x+,r1[lc])+min(y-mid,l1[rc]));

    return res;

}

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);int x,y,z;

        for(int i=;i<=n*;i++)a[i]=-;

        for(int i=;i<=n;i++){

            scanf("%d",&x);Insert(,,n,i,i,x);

        }

        for(I=;I<=m;I++){

            scanf("%d%d%d",&z,&x,&y);x++;y++;

            if(z==||z==||z==)Insert(,,n,x,y,z);

            if(z==)printf("%d\n",Query1(,,n,x,y));

            if(z==)printf("%d\n",Query2(,,n,x,y));

        }

    }

    return ;

}