#include<cstdio>

#define tasu(x) (x&(x-1))
#define ruda(x) ((x|(x-1))+1)

using namespace std;

int a[100010],n;

void adun(int x,int v)
{
    a[x]+=v;
    x=ruda(x);
    while(x<=n)
    {
        a[x]+=v;
        x=ruda(x);
    }
}

int suma(int k)
{
    int s=0;
    while(k)
    {
        s+=a[k];
        k=tasu(k);
    }
    return s;
}

int main()
{
    FILE *f=fopen("aib.in","r"),*g=fopen("aib.out","w");
    int m;
    fscanf(f,"%d%d",&n,&m);
    int i,x,op,a,b;
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d",&x);
        adun(i,x);
    }
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&op,&a);
        if(op-2)fscanf(f,"%d",&b);
        if(op==0)adun(a,b);
        else
            if(op==1)fprintf(g,"%d\n",suma(b)-suma(a-1));
        else
        {
            int li=1,lf=n,mj=(li+lf)/2;
            while(li<=lf)
            {
                if(a<=suma(mj))
                        lf=mj-1;
                else
                    li=mj+1;
                mj=(li+lf)/2;
            }
            if(a==suma(li))
                fprintf(g,"%d\n",li);
            else
                fprintf(g,"-1\n");
        }
    }
    return 0;
}