#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m,a[N], tree[N];

int lobit(int x) {
	return x & -x;
}

void update(int x, int c) {
	for (int i = x; i <= n; i += lobit(i)) {
		tree[i] += c;
	}
}

int query(int x) {
	//查询1~x的区间和
	int res = 0;
	for (int i = x; i >= 1; i -= lobit(i)) {
		res += tree[i];
	}
	return res;
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		update(i, a[i]);
	}
	for (int i = 1; i <= m; i++) {
		int opt, x, y, z;
		cin >> opt >> x >> y;
		if (opt == 1) {
			update(x, y);
		} else
			cout << query(y) - query(x - 1) << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m, a[N], tree[N];

int lobit(int x) {
	return x & -x;
}

void update(int x, int c) {
	for (int i = x; i <= n; i += lobit(i)) {
		tree[i] += c;
	}
}

int query(int x) {
	//查询1~x的区间和
	int res = 0;
	for (int i = x; i >= 1; i -= lobit(i)) {
		res += tree[i];
	}
	return res;
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		update(i, a[i] - a[i - 1]);
	}
	for (int i = 1; i <= m; i++) {
		int opt, x, y, z;
		cin >> opt >> x;
		if (opt == 1) {
			cin >> y >> z;
			update(x, z);
			update(y + 1, -z);
		} else {
			cout << query(x) << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int a[N], tree[N], tree1[N], n, m;

//tree[i] b[i]
//tree1[i] (i-1)*b[i]
int lobit(int x) {
	return x & -x;
}

void update(int x, int c) {
	for (int i = x; i <= n; i += lobit(i)) {
		tree[i] += c;
	}
}

void update1(int x, int c) {
	for (int i = x; i <= n; i += lobit(i)) {
		tree1[i] += c;
	}
}

int query(int x) {
	int res = 0;
	for (int i = x; i >= 1; i -= lobit(i)) {
		res += tree[i];
	}
	return res;
}

int query1(int x) {
	int res = 0;
	for (int i = x; i >= 1; i -= lobit(i)) {
		res += tree1[i];
	}
	return res;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		update(i, a[i] - a[i - 1]);
		update1(i, (a[i] - a[i - 1]) * (i - 1));
	}
	for (int i = 1; i <= m; i++) {
		int opt, x, y, z;
		cin >> opt >> x >> y;
		if (opt == 1) {
			cin >> z;
			update(x, z);
			update(y + 1, -z);
			update1(x, (x - 1)*z);
			update1(y + 1, -y * z);
		} else {
			cout << y *query(y) - query1(y) - ((x - 1)*query(x - 1) - query1(x - 1)) << "\n";
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, tree[4100][4100];

int lobit(int x) {
	return x & -x;
}

void update(int x, int y, int k) {
	for (int i = x; i <= n; i += lobit(i)) {
		for (int j = y; j <= m; j += lobit(j)) {
			tree[i][j] += k;
		}
	}
}

int query(int x, int y) {
	int res = 0;
	for (int i = x; i >= 1; i -= lobit(i)) {
		for (int j = y; j >= 1; j -= lobit(j)) {
			res += tree[i][j];
		}
	}
	return res;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int opt, x, y, x1, y1, z;
	while (cin >> opt) {
		if (opt == 1) {
			cin >> x >> y >> z;
			update(x, y, z);
		} else {
			cin >> x >> y >> x1 >> y1;
			cout << query(x1, y1) - query(x - 1, y1) - query(x1, y - 1) + query(x - 1, y - 1) << endl;
		}
	}
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int tree[N << 2], n, m, a[N];

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int p, int c) {
	if (l == r) {
		tree[rt] += c;
		return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid)
		update(l, mid, rt << 1, p, c);
	else
		update(mid + 1, r, rt << 1 | 1, p, c);
	pushup(rt);
}

int query(int l, int r, int rt, int L, int R) {
	//L--l---r--R
	if (L <= l && r <= R) {
		return tree[rt];
	}
	int res = 0;
	int mid = (l + r) >> 1;
	if (L <= mid)
		res += query(l, mid, rt << 1, L, R);
	if (R > mid)
		res += query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1) {
			update(1, n, 1, x, y);
		} else {
			cout << query(1, n, 1, x, y) << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m, tree[N << 2], tag[N << 2], a[N];

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void pushdown(int l, int r, int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		int mid = (l + r) >> 1;
		tree[rt << 1] += tag[rt] * (mid - l + 1);
		tree[rt << 1 | 1] += tag[rt] * (r - mid);
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		tree[rt] += c * (r - l + 1);
		return;
	}
	pushdown(l, r, rt);
	int mid = (l + r) >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, c);
	pushup(rt);
}

int query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	int res = 0;
	int mid = (l + r) >> 1;
	pushdown(l, r, rt);
	if (L <= mid)
		res += query(l, mid, rt << 1, L, R);
	if (R > mid)
		res += query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, n, 1);
	while (m--) {
		int opt, x, y, z;
		cin >> opt >> x >> y;
		if (opt == 1) {
			cin >>  z;
			update(1, n, 1, x, y, z);
		} else
			cout << query(1, n, 1, x, y) << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

struct node {
	int ch[2], fa;
	int size, cnt, val;
	//ch[2]左右儿子 fa父亲 siz子树大小 cnt节点个数，val值
} tree[N];
int n, m, root, tot;

void pushup(int x) {
	//求节点x的siz
	if (!x)
		return;
	tree[x].size = tree[tree[x].ch[0]].size + tree[tree[x].ch[1]].size + tree[x].cnt;
}

int Get(int x) {
	//判断x是左儿子还是右儿子
	return x == tree[tree[x].fa].ch[1];
}

void rotate(int x) {
	//将x旋转到上面
	int y = tree[x].fa, z = tree[y].fa;
	int chk = Get(x);
	tree[y].ch[chk] = tree[x].ch[chk ^ 1];
	if (tree[x].ch[chk ^ 1])
		tree[tree[x].ch[chk ^ 1]].fa = y;
	tree[x].ch[chk ^ 1] = y;
	tree[y].fa = x;
	if (z)
		tree[z].ch[y == tree[z].ch[1]] = x;
	tree[x].fa = z;
	pushup(y);
	pushup(x);
}

void splay(int x, int k) {
	//将x旋转到k的儿子
	while (tree[x].fa != k) {
		int y = tree[x].fa, z = tree[y].fa;
		if (z != k) {
			if (Get(y) == Get(x))
				rotate(y);
			else
				rotate(x);
		}
		rotate(x);
	}
	if (!k)
		root = x;
}

void insert(int x) {
	int cur = root;
	int fa = 0;
	while (cur) {
		if (tree[cur].val == x) {
			tree[cur].cnt++;
			pushup(cur);
			pushup(fa);
			splay(cur, 0);
			return;
		}
		fa = cur;
		cur = tree[cur].ch[x > tree[cur].val];
	}
	cur = ++tot;
	tree[cur].val = x;
	tree[cur].cnt = 1;
	tree[cur].fa = fa;
	tree[fa].ch[x > tree[fa].val] = cur;
	pushup(cur);
	pushup(fa);
	splay(cur, 0);
}

int rnk(int x) {
	int cur = root;
	int res = 0;
	while (cur) {
		if (x < tree[cur].val)
			cur = tree[cur].ch[0];
		else {
			res += tree[tree[cur].ch[0]].size;
			if (tree[cur].val == x) {
				splay(cur, 0);
				return res + 1;
			} else {
				res += tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return res + 1;
}

int kth(int x) {
	int cur = root;
	while (cur) {
		if (x <= tree[tree[cur].ch[0]].size)
			cur = tree[cur].ch[0];
		else {
			x -= tree[tree[cur].ch[0]].size;
			if (x <= tree[cur].cnt) {
				splay(cur, 0);
				return cur;
			} else {
				x -= tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return -1;
}

int pre(int x) {
	//求x的前驱
	int cur = root;
	int res = -1e9;
	while (cur) {
		if (x <= tree[cur].val) {
			cur = tree[cur].ch[0];
		} else {
			res = max(res, tree[cur].val);
			cur = tree[cur].ch[1];
		}
	}
	return res;
}

int nxt(int x) {
	int cur = root;
	int res = 1e9;
	while (cur) {
		if (x >= tree[cur].val) {
			cur = tree[cur].ch[1];
		} else {
			res = min(res, tree[cur].val);
			cur = tree[cur].ch[0];
		}
	}
	return res;
}

void find(int x) {
	//找x，将x转到根
	int cur = root;
	while (cur) {
		if (tree[cur].val == x) {
			splay(cur, 0);
			return;
		}
		cur = tree[cur].ch[x > tree[cur].val];
	}
}

void del(int x) {
	find(x);
	int L = tree[root].ch[0], R = tree[root].ch[1];
	while (tree[L].ch[1])
		L = tree[L].ch[1];
	while (tree[R].ch[0])
		R = tree[R].ch[0];
	splay(L, 0);
	splay(R, L);
	if (tree[tree[R].ch[0]].cnt > 1) {
		tree[tree[R].ch[0]].cnt--;
		pushup(tree[R].ch[0]);
	} else {
		tree[R].ch[0] = 0;
		pushup(tree[R].ch[0]);
	}
	pushup(R);
	pushup(L);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	insert(-1e9 - 1);
	insert(1e9 + 1);
	for (int i = 1; i <= n; i++) {
		int opt, x;
		cin >> opt >> x;
		if (opt == 1) {
			insert(x);
		} else if (opt == 2) {
			del(x);
		} else if (opt == 3) {
			cout << rnk(x) - 1 << "\n";
		} else if (opt == 4) {
			cout << tree[kth(x + 1)].val << "\n";
		} else if (opt == 5) {
			cout << pre(x) << "\n";
		} else
			cout << nxt(x) << "\n";
	}
	return 0;
}