#include <fstream>

#define X1 262145

using namespace std;

int v[X1];
int N;

inline void update(int nod,int L,int R,int pos,int val)
{
    if(L==R&&L==pos) v[nod]+=val;
    else
    {
        int M=(L+R)/2;

        if(pos<=M) update(2*nod,L,M,pos,val);
        else update(2*nod+1,M+1,R,pos,val);

        v[nod]=v[2*nod]+v[2*nod+1];
    }
}

inline int query(int nod,int L,int R,int a,int b)
{
    if(a<=L&&R<=b) return v[nod];
    else
    {
        int M=(L+R)/2,sum=0;

        if(a<=M) sum+=query(2*nod,L,M,a,b);
        if(b>M) sum+=query(2*nod+1,M+1,R,a,b);

        return sum;
    }
}

inline int BS(int x,int L,int R)
{
    if(L<=R)
    {
        int M=(L+R)/2;
        int val=query(1,1,N,1,M);

        if(x<val) return BS(x,L,M-1);
        else
        if(x>val) return BS(x,M+1,R);
        else return M;
    }
    else return -1;
}

ifstream in;
ofstream out;

int main()
{
    int M,x,tip,a,b;

    in.open("aib.in");
    out.open("aib.out");

    in>>N>>M;
    for(int i=1;i<=N;++i)
        in>>x, update(1,1,N,i,x);

    for(;M;--M)
    {
        in>>tip;
        if(tip==0)
        {
            in>>a>>b;
            update(1,1,N,a,b);
        }
        else
        if(tip==1)
        {
            in>>a>>b;
            out<<query(1,1,N,a,b)<<'\n';
        }
        else
        {
            in>>a;
            out<<BS(a,1,N)<<'\n';
        }
    }
    in.close();
    out.close();

    return 0;
}