#include <cstdio>
#define filein "aib.in"
#define fileout "aib.out"
using namespace std;

int n,q;
int aib[100001];

void Update(int poz,int val);
int Query(int x);
inline int lsb(int x);

int main()
{
    FILE *in,*out;
    in=fopen(filein,"r");
    out=fopen(fileout,"w");
    fscanf(in,"%d%d",&n,&q);
    int i,x,op;
    int a,b,aux;
    int last,st,fn,mij;
    for (i=1;i<=n; i++)
    {
        fscanf(in,"%d",&x);
        Update(i,x);
    }
    for (i=1; i<=q; i++)
    {
        fscanf(in,"%d",&op);
        if (op==0)
        {
            fscanf(in,"%d%d",&a,&b);
            Update(a,b);
        }
        if (op==1)
        {
            fscanf(in,"%d%d",&a,&b);
            fprintf(out,"%d\n",Query(b)-Query(a-1));
        }
        if (op==2)
        {
            fscanf(in,"%d",&a);
            last=-1;
            st=1;
            fn=n;
            while (st<=fn)
            {
                mij=(st+fn)>>1;
                aux=Query(mij);
                if (a<=aux)
                {
                    if (a==aux)
                        last=mij;
                    fn=mij-1;
                }
                else st=mij+1;
            }
            fprintf(out,"%d\n",last);
        }
    }
    return 0;
}

void Update(int poz,int val)
{
    for (; poz<=n; poz+=lsb(poz))
        aib[poz]+=val;
}

int Query(int x)
{
    int s=0;
    for (; x; x-=lsb(x))
        s+=aib[x];
    return s;
}

inline int lsb(int x)
{
    return x&(-x);
}