分块WA20！！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const ll MAXN = 1e6 + 10, INF = 0x3f3f3f3f3f;
ll N, M, X, Y, K, p, q, a[MAXN];
ll L[1010], R[1010], t, g[MAXN], big[1010], add[1010], lazy[1010];
char OP;
void push_down( ll x ) {
	if( lazy[x] == INF ) return;
	for( int i = L[x]; i <= R[x]; i ++ ) a[i] = lazy[x];
	add[x] = 0;
	lazy[x] = INF;
	return;
}
void calm( ll x ) {
	big[x] = -INF;
	for( int i = L[x]; i <= R[x]; i ++ ) big[x] = max( big[x], a[i] + add[x] );
	return;
}
void solute1( ll x, ll y ) {
	p = g[x]; q = g[y];
	if( p == q ) {
		push_down( p );//lazy[p]下放清空 a[i] + add[p]留
		for( int i = x; i <= y; i ++ ) a[i] = K - add[p];
		calm( p );
		return;
	} else {
		for( int i = p + 1; i <= q - 1; i ++ ) { lazy[i] = K, add[i] = 0, big[i] = K; }
		push_down( p );
		for( int i = x; i <= R[p]; i ++ ) a[i] = K - add[p];
		calm( p );
		push_down( q );
		for( int i = L[q]; i <= y; i ++ ) a[i] = K - add[q];
		calm( q );
		return;
	}
}
void solute2( ll x, ll y ) {
	p = g[x]; q = g[y];
	if( p == q ) {
		push_down( p );
		for( int i = x; i <= y; i ++ ) a[i] += K;
		calm( p );
		return;
	} else {
		for( int i = p + 1; i <= q - 1; i ++ ) {
			if( lazy[i] != INF ) push_down( i ), add[i] += K, big[i] += K;
			else add[i] += K, big[i] += K;
		}
		push_down( p );
		for( int i = x; i <= R[p]; i ++ ) a[i] += K;
		calm( p );
		push_down( q );
		for( int i = x; i <= L[q]; i ++ ) a[i] += K;
		calm( q );
		return;
	}
}
ll ask( ll x, ll y ) {
	p = g[x]; q = g[y];
	ll ans = -INF;
	if( p == q ) {
		push_down( p );
		for( int i = x; i <= y; i ++ ) ans = max( ans, a[i] + add[p] );
		return ans;
	} else {
		for( int i = p + 1; i <= q - 1; i ++ ) ans = max( ans, big[i] );
		push_down( p );
		for( int i = x; i <= R[p]; i ++ ) ans = max( ans, a[i] + add[p] );
		push_down( q );
		for( int i = L[q]; i <= y; i ++ ) ans = max( ans, a[i] + add[q] );
		return ans;
	}
}
template<typename tpn>
tpn read(  ) {
	tpn w = 1, rd = 0; char ch = getchar(  );
	while( !isdigit( ch ) ) { if( ch == '-' ) w = -1; ch = getchar(  ); }
	while( isdigit( ch ) ) { rd = rd * 10 + ch - '0'; ch = getchar(  ); }
	return w * rd;
}
int main(  ) {
	freopen( "1.in", "r", stdin );
	freopen( "1.out", "w", stdout );
	N = read<ll>(  ); M = read<ll>(  );
	for( int i = 1; i <= N; i ++ ) a[i] = read<ll>(  );
	t = sqrt( N );
	for( int i = 1; i <= t; i ++ ) L[i] = ( i - 1 ) * t + 1, R[i] = i * t;
	if( R[t] < N ) L[t + 1] = R[t] + 1, R[t + 1] = N, t ++;
	for( int i = 1; i <= t; i ++ ) {
		lazy[i] = INF;
		for( int j = L[i]; j <= R[i]; j ++ ) g[j] = i;
		calm( i );
	}
	for( int i = 1; i <= M; i ++ ) {
		cin>>OP; X = read<ll>(  ); Y = read<ll>(  );
		if( OP == '1' ) K = read<ll>(  ), solute1( X, Y );
		else if( OP == '2' ) K = read<ll>(  ), solute2( X, Y );
		else cout<<ask( X, Y )<<endl;
	}
	return 0;
}