#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
#include <iostream>
using namespace std;
#define FOR(i,a,b) for (i=a;i<=b;i++)
#define fori(it,v) for (it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
#define cnt 1<<20
unsigned int arb[100005];
int n;
int bit(int x)
{
	return (x&(x-1))^x;
}
unsigned int query(int x)
{
	 if (x==0)
		 return 0;
	 return arb[x]+query(x-bit(x));
}
void adauga(int x,int y)
{
	arb[x]+=y;
	while((x+=bit(x))<=n)
	{
		arb[x]+=y;
	}

}
int ver(int rez,unsigned int  x)
{
	if (rez>n)
		return 1;
	if (query(rez)>=x)
		return 1;
	return 0;
}
void afis()
{
	int i;
	FOR(i,1,n)
		printf("%d ",arb[i]);
	printf("\n");
}
int main()
{
	FILE *in,*out;
	int x,y,i,m,j;
	unsigned int rez,z;
	in=fopen("aib.in","r");
	out=fopen("aib.out","w");
	fscanf(in,"%d%d",&n,&m);
	FOR(i,1,n)
	{
		fscanf(in,"%d",&x);
		adauga(i,x);
	}
	//afis();
	FOR(i,1,m)
	{
		fscanf(in,"%d",&x);
		if (x==0)
		{
			fscanf(in,"%d%d",&x,&y);
			adauga(x,y);
			continue;
		}
		if (x==1)
		{
			fscanf(in,"%d%d",&x,&y);
			fprintf(out,"%u\n",query(y)-query(x-1));
			continue ;
		}
		fscanf(in,"%u",&z);
		rez=0;
		for(j=cnt;j;j>>=1)
		{
			rez+=j;
			if (ver(rez,z))
				rez-=j;
		}
		rez++;
		if (query(rez)!=z)
			fprintf(out,"-1\n");
		else
			fprintf(out,"%u\n",rez);
	
	}
	fclose(in);
	fclose(out);
	return 0;
}