• 转换成一个数在(0,X + Y)的加减问题
• 考虑一种使用线段树处理的方法， 维护前缀最大值， 前缀最小值， 前缀和， 然后查询的时候先询问右区间是否会同时碰到上下界， 会的话左区间无用直接递归右区间， 否则的话递归左区间， 然后右区间只会碰到上边界或者下边界， 分两种情况讨论即可

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define M 500010

#define ls now << 1

#define rs now << 1 | 1

#define lson l, mid, now << 1

#define rson mid + 1, r, now << 1 | 1

#define ll long long

#define mmp make_pair

using namespace std;

int read() {

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int n, q, x, y, z;

ll sum[M << 2], minn[M << 2], maxx[M << 2];

void pushup(int now) {

	sum[now] = sum[ls] + sum[rs];

	minn[now] = min(minn[ls], sum[ls] + minn[rs]);

	maxx[now] = max(maxx[ls], sum[ls] + maxx[rs]);

}

void modify(int l, int r, int now, int pl, int v) {

	if(l > pl || r < pl) return;

	if(l == r) {

		sum[now] = v;

		minn[now] = min(v, 0);

		maxx[now] = max(v, 0);

		return;

	}

	int mid = (l + r) >> 1;

	modify(lson, pl, v), modify(rson, pl, v);

	pushup(now);

}

ll s;

ll merge(ll v, int now) {

	if(v + maxx[now] > s) return s - maxx[now] + sum[now];

	if(v + minn[now] < 0) return sum[now] - minn[now];

	return v + sum[now];

}

ll query(int l, int r, int now, ll v) {

	if(l == r) return max(min(s, sum[now] + v), 0ll);

	int mid = (l + r) >> 1;

	if(maxx[rs] - minn[rs] > s) return query(rson, 0);

	else return merge(query(lson, v), rs);

}

int main() {

//	freopen("stone1.in", "r", stdin);

	n = read(), q = read();

	x = read(), y = read();

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

		z = read();

		if(i % 2 == 0) z = -z;

		modify(1, n, 1, i, z);

	}

	while(q--) {

		int op = read();

		if(op == 1) x = read();

		else if(op == 2) y = read();

		else {

			int pl = read(), v = read();

			if(pl % 2 == 0) v = -v;

			modify(1, n, 1, pl, v);

		}

		s = x + y;

		cout << query(1, n, 1, x) << "\n";

	}

	return 0;

}