#include <fstream>
#define N 100010

std::ifstream in ("aib.in");
std::ofstream out ("aib.out");
int aib[N],n,m,i,x,y;

int query (int p) {
	int r=0;
	do {
		r+=aib[p];
	} while (p&=p-1);
	return r;
}

void update (int p) {
	aib[p]+=y;
	while ((p+=p&-p)<=n) aib[p]+=y;
}

int bsearch (int l,int r) {
	i=(l+r)/2;
	y=query (i);
	if (l==r)
		if (y==x) return l;
		else
			if (y==query (l+1)) return l+1;
			else return -1;
	if (x<=y) return bsearch (l,i);
	return bsearch (i+1,r);
}

int main (int argc, char **args) {
	in>>n>>m;
	for (x=1; x<=n; x++) {
		in>>y;
		update (x);
	}
	while (m--) {
		in>>i>>x;
		if (i==0) {
			in>>y;
			update (x);
		}
		else
			if (i==1) {
				in>>y;
				out<<query (y)-query (x-1)<<"\n";
			}
			else out<<bsearch (1,n)<<"\n";
	}
	return 0;
}