#include <stdio.h>

#define pow(x) (x^(x-1))&x
const int nmax=100001;
int aib[nmax];
int n;

void update(int pos, int val)
{
    int i;
    for (i=pos; i<=n; i+=pow(i))
        aib[i]+=val;
}

int compute(int x)
{
    int rez,i;
    rez=0;
    for (i=x; i>0; i-=pow(i))
        rez+=aib[i];
    return rez;
}

int bin_search(int i, int j, int s)
{
    int st,dr,mj,ans,aux;

    st=i;
    dr=j;
    ans=-1;
    while (st <= dr)
    {
        mj=st+(dr-st)/2;
        aux=compute(mj);
        if (aux == s)
        {
             ans=mj;
             st=1;
             dr=0;
        }
        else
            if (aux < s)
                st=mj+1;
            else
                dr=mj-1;
    }
    return ans;
}

int main()
{
    FILE *f,*fout;
    int m,i,x,y,z;

    f=fopen("aib.in","r");
    fout=fopen("aib.out","w");
    fscanf(f,"%d%d",&n,&m);
    for (i=1; i<=n; i++)
    {
        fscanf(f,"%d",&x);
        update(i,x);
    }
    for (i=1; i<=m; i++)
    {
        fscanf(f,"%d",&x);
        if (!x)
        {
            fscanf(f,"%d%d",&y,&z);
            update(y,z);
        }
        else if (x == 1)
        {
            fscanf(f,"%d%d",&y,&z);
            fprintf(fout,"%d\n",compute(z)-compute(y-1));
        }
        else
        {
            fscanf(f,"%d",&y);
            fprintf(fout,"%d\n",bin_search(1,n,y));
        }
    }
}