rt,P1253 50pts

#include <iostream>
using namespace std;
typedef long long ll;
int n, m, op, x, y;
ll k, a[1000001];
const ll inf = -1e18;
struct tree{ll w, lzy_add, lzy_num;}t[4000001];
void maketag(int op, int u, ll x)
{
	if (op == 1)
	{
	    t[u].lzy_add = 0;
	    t[u].lzy_num = x;
	    t[u].w = x;
	}
	else
	{
	    if (t[u].lzy_num == inf) t[u].lzy_add += x;
	    else t[u].lzy_num += x;
	    t[u].w += x;
	}
}
void pushup(int u) {t[u].w = max(t[u << 1].w, t[u << 1 | 1].w);}
void pushdown(int u)
{
	if (t[u].lzy_num == inf)
	{
	    maketag(2, u << 1, t[u].lzy_add);
	    maketag(2, u << 1 | 1, t[u].lzy_add);
	    t[u].lzy_add = 0;
	}
	else
	{
	    maketag(1, u << 1, t[u].lzy_num);
	    maketag(1, u << 1 | 1, t[u].lzy_num);
	    t[u].lzy_num = inf;
	}
}
bool is_in(int l, int r, int L, int R){return (L <= l) && (r <= R);}
bool is_out(int l, int r, int L, int R){return (l > R) || (r < L);}
void build(int u, int l, int r)
{
	t[u].lzy_num = inf;
	if (l == r)
	{
		t[u].w = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}
void update(int op, int u, int l, int r, int L, int R, ll x)
{
	if (is_in(l, r, L, R)) maketag(op, u, x);
	else if (!is_out(l, r, L, R))
	{
		int mid = (l + r) >> 1;
		pushdown(u);
		update(op, u << 1, l, mid, L, R, x);
		update(op, u << 1 | 1, mid + 1, r, L, R, x);
		pushup(u);
	}
}
ll query(int u, int l, int r, int L, int R)
{
	if (is_in(l, r, L, R)) return t[u].w;
	else if (is_out(l, r, L, R)) return 0;
	else
	{
		int mid = (l + r) >> 1;
		pushdown(u);
		return max(query(u << 1, l, mid, L, R), query(u << 1 | 1, mid + 1, r, L, R));
	}
}
ll read()
{
	ll s = 0, w = 1;
	char c = getchar_unlocked();
	while (c < '0' || c > '9')
	{
		if (c == '-') w = -1;
		c = getchar_unlocked();
	}
	while (c >= '0' && c <= '9')
	{
		s = s * 10 + c - '0';
		c = getchar_unlocked();
	}
	return s * w;
}
void write(ll n)
{
	if (n < 0) 
	{
		putchar_unlocked('-');
		n = -n;
	}
	if (n >= 10) write(n / 10);
	putchar_unlocked(n % 10 + '0');
	return;
}
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	build(1, 1, n);
	while (m--)
	{
		op = read();
		if (op == 1)
		{
			x = read(), y = read(), k = read();
			update(1, 1, 1, n, x, y, k);
		}
		else if (op == 2)
		{
		    x = read(), y = read(), k = read();
			update(2, 1, 1, n, x, y, k);
		}
		else
		{
			x = read(), y = read();
			write(query(1, 1, n, x, y));
			putchar_unlocked('\n');
		}
	}
	return 0;
}