#include<fstream>
using namespace std;
int n, m, i, x, tip, poz, a, b, v[100005];

void adauga(int poz, int val){
	while (poz <= n){
		v[poz] += val;

		poz += (poz^(poz-1)) & poz;
	}
}
int cat(int poz){
	int rez = 0;

	while (poz > 0){
		rez += v[poz];

		poz -= (poz^(poz-1)) & poz;
	}

	return rez;
}
int caut_binar(int val){
	int li = 1, ls = n, x, gasit = -1;

	while (li <= ls){
		x = (li+ls) / 2;

		a = cat(x);
		if (a >= val){
			if (a == val)
				gasit = x;
			ls = x-1;
		}
		else
			li = x+1;
	}

	return gasit;
}

int main()
{
	ifstream f("aib.in");
	ofstream g("aib.out");

    f>>n>>m;

	for (i = 1; i <= n; i ++){
		f>>x;

		adauga(i, x);
	}

	for (i = 1; i <= m; i ++){
		f>>tip;

		if (tip == 0){
			f>>poz>>x;

			adauga(poz, x);
			continue;
		}
		if (tip == 1){
			f>>a>>b;

			g<<cat(b)-cat(a-1)<<"\n";
		}
		if (tip == 2){
			f>>a;

			g<<caut_binar(a)<<"\n";
		}
	}

	return 0;
}