#include <iostream>
#include <cstdio>
#define D (1<<18)
using namespace std;
FILE* f=fopen("aib.in","r");
FILE* g=fopen("aib.out","w");
int n,m,a[D-25],val,poz,t,s,first,last,b,x;
void update(int rad,int st,int dr,int b)
{
    if(st==dr)
    {
        if(b==0)
            a[rad]=val;
        else
            a[rad]+=b;
        return;
    }
    int mij=((st+dr)>>1);
    if(poz<=mij)
        update((rad<<1),st,mij,b);
    if(poz>mij)
        update((rad<<1)+1,mij+1,dr,b);
    a[rad]=a[(rad<<1)]+a[1+(rad<<1)];
}
void parc(int rad, int st, int dr)
{
    if(first<=st and dr<=last)
    {
        s+=a[rad];
            return;
    }
    int mij=((st+dr)>>1);
    if(mij>=first)
        parc((rad<<1),st,mij);
    if(mij<last)
        parc((rad<<1)+1,mij+1,dr);

}
int cautBin(int st,int dr,int o)
{
    s=0;
    int mij=((st+dr)>>1);
    first=1,last=mij;
    parc(1,1,n);
    if(st==dr)
    {
        if(s==o)
            return last;
        else return -1;
    }
    if(o<=s)
        return cautBin(st,mij,o);
    else return cautBin(mij+1,dr,o);
}
int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        fscanf(f,"%d",&val);
        poz=i;
        update(1,1,n,0);
    }
    for(int i=0;i<m;i++)
    {
        fscanf(f,"%d",&t);
        switch(t)
        {
            case 1:
            {
                s=0;
                fscanf(f,"%d%d",&val,&b);
                first=val;
                last=b;
                parc(1,1,n);
                fprintf(g,"%d\n",s);
                break;
            }
            case 2:
            {
                fscanf(f,"%d",&b);
                int u=cautBin(1,n,b);
                fprintf(g,"%d\n",u);
                break;
            }
            case 0:
            {
                fscanf(f,"%d%d",&poz,&b);
                update(1,1,n,b);
                break;
            }
        }
    }
    return 0;
}