#include<fstream>
#include<iostream>
using namespace std;
#define MAX 100001

int N,M,bit[MAX];

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

void update(int p,int val)
{
	int ind=p;
	while(ind<=N)
	{
		bit[ind]+=val;
		ind +=ind&(-ind);
	}
}
int getSum(int e)
{
	int ind=e,s=0;
	while(ind>0)
	{
		s+=bit[ind];
		ind-=ind&(-ind);
	}
	return s;
}

int minK(int a)
{
	int st=1,dr=N,mid,k;
	while(st<=dr)
	{
		mid=(st+dr)/2;
		k=getSum(mid);
		if(k==a)
			return mid;
		else if(a<k)
			dr=mid-1;
		else
			st=mid+1;
	}
	return -1;
}
int main()
{
	in>>N>>M;
	int op,a,b;
	for(int i=1;i<=N;i++)
	{
		in>>a;
		update(i,a);
	}
	for(int j=1;j<=M;j++)
	{
		in>>op;
		switch(op)
		{
		case 0:
			in>>a>>b;
			update(a,b);
			break;
		case 1:
			in>>a>>b;
			out<<getSum(b)-getSum(a-1)<<'\n';
			break;
		case 2:
			in>>a;
			out<<minK(a)<<'\n';
			break;
		}
	}
	return 0;
}