#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 100005
#define LSB(x) ((x^(x-1))&x)
using namespace std;

FILE *IN,*OUT;

int AIB[MaxN],N,M,Type,X,Y;

void Update(int pos,int val)
{
	for(int x=pos;x<=N;x+=LSB(x))
		AIB[x]+=val;
}
int Query(int pos)
{
	int Sum=0;
	for(int x=pos;x>0;x-=LSB(x))
		Sum+=AIB[x];
	return Sum;
}
int Query2(int Val)
{
	int Pos=0;
	for(int i=30;i>=0;i--)
	{
		if((1<<i)+Pos<=N&&AIB[(1<<i)+Pos]<=Val)
		{
			Pos+=(1<<i),Val-=AIB[Pos];
			if(Val==0)
				return Pos;
		}
	}
	return -1;
}
int main()
{
	IN=fopen("aib.in","r");
	OUT=fopen("aib.out","w");
	
	fscanf(IN,"%d%d",&N,&M);
	for(int i=1;i<=N;i++)
	{
		fscanf(IN,"%d",&X);
		Update(i,X);
	}
	for(int i=1;i<=M;i++)
	{
		fscanf(IN,"%d",&Type);
		if(Type==0)
		{
			fscanf(IN,"%d%d",&X,&Y);
			Update(X,Y);
		}
		else if(Type==1)
		{
			fscanf(IN,"%d%d",&X,&Y);
			fprintf(OUT,"%d\n",Query(Y)-Query(X-1));
		}
		else 
		{
			fscanf(IN,"%d",&X);
			fprintf(OUT,"%d\n",Query2(X));
		}
	}
	return 0;
}