1 //必须使用C++编译器
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<cmath>
  7 using namespace std;
  8 typedef long long ll;
  9 const int maxn = 1000100;
 10 #define ls(p) p<<1
 11 #define rs(p) p<<1|1
 12 int a[maxn] , n , m;
 13 int mx[maxn<<2] , cnt[maxn<<2] , se[maxn<<2] , add[maxn<<2];
 14 ll sum[maxn<<2];
 15 void push_up(int p)
 16 {
 17     sum[p] = sum[ls(p)] + sum[rs(p)];
 18     if(mx[ls(p)] == mx[rs(p)])
 19     {
 20         se[p] = max(se[ls(p)] , se[rs(p)]);
 21         mx[p] = mx[ls(p)];
 22         cnt[p] = cnt[ls(p)] + cnt[rs(p)];
 23     }
 24     else if(mx[ls(p)] > mx[rs(p)])
 25     {
 26         se[p] = max(se[ls(p)] , mx[rs(p)]);
 27         mx[p] = mx[ls(p)];
 28         cnt[p] = cnt[ls(p)];
 29     }
 30     else
 31     {
 32         se[p] = max(se[rs(p)] , mx[ls(p)]);
 33         mx[p] = mx[rs(p)];
 34         cnt[p] = cnt[rs(p)];
 35     }
 36 }
 37 void push_down(int p)
 38 {
 39     if(add[p] == -1) return ;  // 区间覆盖
 40     int& t = add[p];
 41     if(mx[ls(p)] > t && t > se[ls(p)])
 42     {
 43         sum[ls(p)] -= 1ll*(mx[ls(p)]-t)*cnt[ls(p)];
 44         add[ls(p)] = mx[ls(p)] = t;
 45     }
 46     if(mx[rs(p)] > t && t > se[rs(p)])
 47     {
 48         sum[rs(p)] -= 1ll*(mx[rs(p)]-t)*cnt[rs(p)];
 49         add[rs(p)] = mx[rs(p)] = t;
 50     }
 51     t = -1;
 52 }
 53 void build(int p , int pl , int pr)
 54 {
 55     add[p] = -1;
 56     if(pl == pr)
 57     {
 58         se[p] = -1; cnt[p] = 1;
 59         sum[p] = mx[p] = a[pl];
 60         return ;
 61     }
 62     int mid = pl+pr >> 1;
 63     build(ls(p) , pl , mid);
 64     build(rs(p) , mid+1 , pr);
 65     push_up(p);
 66 }
 67 void update(int L , int R, int p , int pl, int pr , int t)
 68 {
 69     if(mx[p] <= t) return ;
 70     if(L <= pl && pr <= R && se[p] < t)
 71     {
 72         sum[p] -= 1ll*(mx[p]-t)*cnt[p];
 73         mx[p] = add[p] = t;
 74         return ;
 75     }
 76     int mid = pl+pr >> 1;
 77     push_down(p);
 78     if(L <= mid) update(L , R , ls(p) , pl , mid , t);
 79     if(R > mid)  update(L , R , rs(p) , mid+1 , pr , t);
 80     push_up(p);
 81 }
 82 int query_max(int L , int R , int p , int pl , int pr)
 83 {
 84     if(L <= pl && pr <= R) return mx[p];
 85     int mid = pl+pr >> 1;
 86     int ans = 0;
 87     push_down(p);
 88     if(L <= mid) ans = max(ans , query_max(L , R , ls(p) , pl , mid));
 89     if(R > mid)  ans = max(ans , query_max(L , R , rs(p) , mid+1 , pr));
 90     return ans;
 91 }
 92 ll query_sum(int L , int R , int p , int pl , int pr)
 93 {
 94     if(L <= pl && pr <= R) return sum[p];
 95     int mid = pl+pr >> 1;
 96     ll ans = 0;
 97     push_down(p);
 98     if(L <= mid) ans += query_sum(L , R , ls(p) , pl , mid);
 99     if(R > mid)  ans += query_sum(L , R , rs(p) , mid+1 , pr);
100     return ans;
101 }
102 int main()
103 {
104     int t;
105     scanf("%d",&t);
106     while(t--)
107     {
108         scanf("%d%d",&n,&m);
109         for(int i = 1; i <= n; i++)
110             scanf("%d",&a[i]);
111         build(1,1,n);
112         for(int i = 1;i <= m; i++)
113         {
114             int opt , L , R , k;
115             scanf("%d",&opt);
116             if(opt == 0)
117             {
118                 scanf("%d%d%d",&L,&R,&k);
119                 if(L > R) swap(L , R);
120                 update(L , R , 1 , 1 , n , k);
121             }
122             else if(opt == 1)
123             {
124                 scanf("%d%d",&L,&R);
125                 if(L > R) swap(L , R);
126                 printf("%d\n",query_max(L,R,1,1,n));
127             }
128             else if(opt == 2)
129             {
130                 scanf("%d%d",&L,&R);
131                 if(L > R) swap(L , R);
132                 printf("%lld\n",query_sum(L,R,1,1,n));
133             }
134         }
135     }
136     return 0;
137 }