#include <stdio.h>
#include <vector>

using namespace std;

void update(vector<int> &tree, int delta, int index)
{
	int n = (int) tree.size();

	// modific nodurile de pe acelasi nivel din dreapta si cel cu prima
	// putere a lui 2 mai mare ca i; valorile din copiii sau parintii
	// nodului index nu sunt schimbate
	for (int i = index; i < n; i += i & -i)
		tree[i] += delta;
}

int rangesum(const vector<int> &tree, int i, int j)
{
	--i;
	int sum = 0;

	while (j > i) {
		sum += tree[j];
		j -= (j & -j);
	}

	while (i > j) {
		sum -= tree[i];
		i -= (i & -i);
	}

	return sum;
}

int search_pos(vector<int> &tree, int k)
{
	int n = (int) tree.size();
	int jump = 1;

	while (jump < n)
		jump <<= 1;

	int i = 0;

	while (jump != 0) {
		if (i + jump < n) {
			if (k >= tree[i + jump]) {
				k -= tree[i + jump];
				i += jump;

				if (k == 0)
					return i;
			}
		}

		jump >>= 1;
	}

	return -1;
}

int main()
{
	FILE *fin = fopen("aib.in", "r");
	FILE *fout = fopen("aib.out", "w");
	int i, n, m;

	fscanf(fin, "%d%d", &n, &m);
	vector<int> tree(n + 1, 0);
	int x;

	for (i = 0; i < n; i++) {
		fscanf(fin, "%d", &x);
		update(tree, x, i + 1);
	}

	int op;
	int a, b;

	for (i = 0; i < m; i++) {
		fscanf(fin, "%d", &op);

		switch (op) {
		case 0:
			fscanf(fin, "%d%d", &a, &b);
			update(tree, b, a);
			break;
		case 1:
			fscanf(fin, "%d%d", &a, &b);
			fprintf(fout, "%d\n", rangesum(tree, a, b));
			break;
		case 2:
			fscanf(fin, "%d", &a);
			fprintf(fout, "%d\n", search_pos(tree, a));
		default:
			break;
		}
	}

	int ret;

	ret = fclose(fin);
	if (ret)
		return ret;
	ret = fclose(fout);
	if (ret)
		return ret;
	return 0;
}