#include <cstdio>
#define bit(i) ( (i) & ((i)-1)^(i))
#define maxn 100001
#define DIM (1<<13)

char ax[DIM];
int poz;
int aib[maxn];

int n;


inline void cit(int &x)
{
	x=0;
	while(ax[poz]<'0' || ax[poz]>'9') 
	{
		++poz;
		if(poz==DIM) fread(ax, 1, DIM, stdin), poz=0;
	}
	while(ax[poz]>='0' && ax[poz]<='9')
	{
		x=10*x+ax[poz++]-'0';
		if(poz==DIM) fread(ax, 1, DIM, stdin), poz=0;
	}
}

inline void update(int x, int v)
{
    for(;x<=n;x+=bit(x)) aib[x]+=v;
}

inline int query(int x)
{
    int s=0;
    for(;x;x-=bit(x)) s+=aib[x];
    return s;
}

inline int find(int v)
{
    int i, cnt;
    for(i=0, cnt=(1<<18); cnt ; cnt>>=1)
	if(i+cnt<=n)
	    if(v>=aib[i+cnt])
		i+=cnt, v-=aib[i];
    if(!v) return i;
    return -1;
}

inline void scrie(int k)
{
	char lin[30], *s;
	s=lin+29;
	s[0]=0;
	do
	{
		int cat=k/10;
		--s;
		s[0]=k-cat*10+'0';
		k=cat;
	}while(k);
	puts(s);
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int m,i,v, type, p, q;
	cit(n); cit(m);
  //  scanf("%d %d\n",&n, &m);
    for(i=1;i<=n;++i)
    {
		cit(v);
	//	scanf("%d ", &v);
	update(i, v);
    }

    while(m--)
    {
		cit(type);
	//scanf("%d ", &type);
	if(type==0)
	{
		cit(p);cit(q);
		//scanf("%d %d\n", &p, &q);
	    update(p, q);
	}
	if(type==1)
	{
		cit(p); cit(q);
	    //scanf("%d %d\n", &p, &q);
	   scrie(query(q)-query(p-1));
		//printf("%d\n", query(q)-query(p-1));
	}
	if(type==2)
	{
		cit(p);
	    //scanf("%d\n", &p);
	    if(p==0) scrie(-1);//printf("-1\n");
	    else 
	    scrie(find(p));//printf("%d\n",find(p)); 
	}


    }

    return 0;
}