#include <fstream>

using namespace std;

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

const int N=100001;

int n,m;
int v[N],s[N];

void aduna(int poz,int val){
	if(poz>n)
		return;
	v[poz]+=val;
	poz+=(poz-(poz&(poz-1)));
	aduna(poz,val);
}

int kterm(int k){
	int s=0;
	if(k==0)
		return 0;
	s+=v[k];
	k-=(k-(k&(k-1)));
	s+=kterm(k);
	return s;
}	

int suma(int a,int b){
	int s1,s2;
	s1=kterm(b);
	s2=kterm(a-1);
	return (s2-s1);
}

int cauta(int a){
	int pas,poz=-1;
	for(pas=1;pas<=n;pas<<=1);
	for(int i=0;pas;pas>>=1){
		if(kterm(i+pas)==a && i+pas<=n){
			poz=i+pas;
			break;
		}
		if(kterm(i+pas)<a && i+pas<=n){
			i+=pas;
		}
	}
	return poz;
}

int main(){
	int i,j,x;
	in>>n>>m;
	for(i=1;i<=n;++i){
		in>>x;
		aduna(i,x);
	}
	int tip,a,b,aux;
	for(i=1;i<=m;i++){
		in>>tip;
		if(tip==0){
			in>>a>>b;
			aduna(a,b);
		}
		if(tip==1){
			in>>a>>b;
			out<<abs(suma(a,b))<<"\n";
		}
		if(tip==2){
			in>>a;
			out<<cauta(a)<<"\n";
		}
	}
	return 0;
}