#include <fstream>
using namespace std;

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

const int valmax = 10003;
int n,m,aib[100007];

void update (int val, int poz) {
	while (poz <= valmax) {
		aib[poz] += val;
		poz += poz & (-poz);
	}
}

int suma (int poz) {
	int s = 0;
	while (poz) {
		s += aib[poz];
		poz &= poz - 1;
	}
	return s;
}

int bs (int val) {
	int i = 0,step = 1<<17;
	for (; step; step >>= 1) {
		if (i + step <= valmax && suma (i + step) < val) {
			i += step;
		}
	}
	return i+1;
}

int main () {
	in >> n >>m;
	for (int i = 1,x; i <= n; ++i) {
		in >> x;
		update (x,i);
	}
	for (int i = 1,tip,a,b; i <= m; ++i) {
		in >> tip;
		if (tip == 0) {
			in >> a >> b;
			update(b,a);
			continue;
		}
		if (tip == 1) {
			in >> a >> b;
			out << suma (b) - suma (a - 1) << '\n';
			continue;
		}
		in >> a;
		b= bs(a);
		if (suma(b) == a) {
			out << b << "\n";
		}else{
			out<<"-1\n";
		}
	}
	return 0;
}