#include <bits/stdc++.h>

using namespace std;

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

int v[200005],arb[200005];

int lsb(int i)
{
	 return i&(-i); 
}
void Update(int pos,int val,int n)
{
	while(pos<=n)
	{
		arb[pos]+=val;
		pos+=lsb(pos); 
	}
}

int Query(int poz)
{
	int s=0;
	while(poz)
	{
		s+=arb[poz];
		poz-=lsb(poz); 
	}
	return s;
}	


int main()
{
	int n,m;
	in>>n>>m;
	for(int i=1;i<=n;i++)
	{
		in>>v[i];
		Update(i,v[i],n);
	}
	while(m--)
	{
		int cod;
		in>>cod;
		if(cod==0)
		{
			int x,y;
			in>>x>>y;
			Update(x,y,n);
		}
		else if(cod==1)
		{
			int x,y;
			in>>x>>y;
			out<<Query(y)-Query(x-1)<<"\n";
		}
		else
		{
			int x;
			in>>x;
			int st=1,dr=n,ans=-1;
			while(st<=dr && ans==-1)
			{
				int mid=(st+dr)/2;
				int s=Query(mid);
				if(s==x) ans=mid;
				else if(s>x) dr=mid-1;
				else st=mid+1;
			}
			out<<ans<<"\n";
		}
	}
	return 0;
}