#include <bits/stdc++.h>

using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");


const int NMax = 100003;
int arr[NMax], BIT[NMax], n, m;

int getParent(int index)
{
	return index - (index & -index);
}

int getNext(int index)
{
	return index + (index & -index);
}

void updateBIT(int val, int index)
{
	while(index <= n) {
		BIT[index] += val;
		index = getNext(index);
	}
}

void createBIT()
{
	for(int i = 1; i <= n; ++i)
		updateBIT(arr[i], i);
}

int getSum(int index)
{
	int sum = 0;

	while(index > 0) {
		sum += BIT[index];
		index = getParent(index);
	}

	return sum;
}

int findSum(int sum)
{
	int step = (1 << 30);

	for(int i = 0; step; step >>= 1) {
		if(i + step <= n) {
			if(getSum(i + step) == sum)
				return i + step;
			if(getSum(i + step) < sum)
				step += i;
		}
	}

	return -1;
}

int main()
{
	in >> n >> m;

	for(int i = 1; i <= n; ++i)
		in >> arr[i];

	createBIT();

	for(int i = 1; i <= m; ++i) {
		int op, a, b;
		in >> op;

		if(op == 0) {
			in >> a >> b;
			updateBIT(b, a);
		} else {
			if(op == 1) {
				in >> a >> b;
				out << getSum(b) - getSum(a - 1) << '\n';
			}
			else {
				in >> a;
				out << findSum(a) << '\n';
			}
		}
	}

	return 0;
}