（调了半个月了……）

#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffffffffffff
struct node
{
	long long lazy1, lazy2, maxx;
	int l, r;
	node* lchild, * rchild;
	node(int L = 0, int R = 0)
	{
		lazy1 = maxx = 0;
		lazy2 = inf;
		l = L;
		r = R;
		lchild = rchild = 0;
	}
};
long long a[1000010];
int n, q;
node* root;
void make_tree(node*& it, long long l, long long r)
{
	it = new node(l, r);
	if (l == r)
		it->maxx = a[l];
	else
	{
		int mid = l + r >> 1;
		make_tree(it->lchild, l, mid);
		make_tree(it->rchild, mid + 1, r);
		it->maxx = max(it->lchild->maxx, it->rchild->maxx);
	}
}
void push_down(node* it)
{
	if(it)
	{
		if (it->lazy2 != inf)
		{
			if (it->lchild)
			{
				it->lchild->lazy2 = it->lazy2;
				it->lchild->maxx = it->lazy2;
			}
			if (it->rchild)
			{
				it->rchild->lazy2 = it->lazy2;
				it->rchild->maxx = it->lazy2;
			}
			it->lazy2 = inf;
		}
		else
		{
			if (it->lchild)
			{
				it->lchild->lazy1 += it->lazy1;
				it->lchild->maxx += it->lazy1;
			}
			if (it->rchild)
			{
				it->rchild->lazy1 += it->lazy1;
				it->rchild->maxx += it->lazy1;
			}
			it->lazy1 = 0;
		}
	}
	return;
}
void p1(node* it, int r1, int r2, long long k)
{
	push_down(it);
	if (r1 <= it->l && it->r <= r2)
	{
		it->lazy2 = k;
		it->maxx = k;
		it->lazy1 = 0;
		return;
	}
	int mid = it->l + it->r >> 1;
	if (r2 < it->l || r1 > it->r)return;
	if (r1 <= mid)p1(it->lchild, r1, r2, k);
	if (r2 > mid)p1(it->rchild, r1, r2, k);
	it->maxx = max(it->lchild->maxx, it->rchild->maxx);
	return;
}
void p2(node* it, int r1, int r2, long long k)
{
	push_down(it);
	if (r1 <= it->l && it->r <= r2)
	{
		if (it->lazy2 != inf)
			it->lazy2 += it->lazy1;
		else
			it->lazy1 += k;
		it->maxx += k;
		return;
	}
	if (r2 < it->l || r1 > it->r)return;
	int mid = it->l + it->r >> 1;
	if (r1 <= mid)p2(it->lchild, r1, r2, k);
	if (r2 > mid)p2(it->rchild, r1, r2, k);
	it->maxx = max(it->lchild->maxx, it->rchild->maxx);
	return;
}
long long f(node* it, int r1, int r2)
{
	push_down(it);
	if (r1 <= it->l && it->r <= r2)
	{
		return it->maxx;
	}
	if (r2 < it->l || r1 > it->r)return -inf;
	int mid = it->l + it->r >> 1;
	long long ans = -inf;
	if (r1 <= mid)ans = max(ans, f(it->lchild, r1, r2));
	if (r2 > mid)ans = max(ans, f(it->rchild, r1, r2));
	return ans;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	make_tree(root, 1, n);
	for (int i = 1; i <= q; i++)
	{
		int op, l, r;
		long long x;
		scanf("%d %d %d", &op, &l, &r);
		if (op != 3)
			scanf("%lld", &x);
		switch (op)
		{
		case 1:
			p1(root, l, r, x);
			break;
		case 2:
			p2(root, l, r, x);
			break;
		case 3:
			printf("%lld\n", f(root, l, r));
		}
	}
	return 0;
}