#include <fstream>
#define Nmax 100005
#define Lg 600000
#define verf ++poz==Lg? fin.read(Buffer,Lg), poz=0:0

using namespace std;
ifstream fin("aib.in");
int v[Nmax],N,poz;
char Buffer[Lg];

inline void Read(int &x)
{
    for(; Buffer[poz]<'0' || Buffer[poz]>'9'; verf);
    for(x=0; Buffer[poz]>='0' && Buffer[poz]<='9'; x=x*10+Buffer[poz]-'0', verf);
}

inline void Add(int p,int x)
{
    int k;
    while(p<=N)
    {
        v[p]+=x;
        k=0;
        while((p&(1<<k))==0)
            k++;
        p+=(1<<k);
    }
}

inline int Query(int p)
{
    int k,suma=0;
    while(p>0)
    {
        suma+=v[p];
        k=0;
        while((p&(1<<k))==0)
            k++;
        p-=(1<<k);
    }
    return suma;
}

inline int BSearch(int a)
{
    int st,dr,mij,x;
    st=1;dr=N;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        x=Query(mij);
        if(x==a)
            return mij;
        if(x<a)
            st=mij+1;
        else
            dr=mij-1;
    }
    return -1;
}

int main()
{
    int M,i,x,y,tip,sol;
    ofstream fout("aib.out");
    Read(N); Read(M);
    for(i=1;i<=N;++i)
    {
        Read(x);
        Add(i,x);
    }
    while(M--)
    {
        Read(tip);
        if(tip==0)
        {
            Read(x); Read(y);
            Add(x,y);
        }
        else
            if(tip==1)
            {
                Read(x); Read(y);
                sol=Query(y)-Query(x-1);
                fout<<sol<<"\n";
            }
            else
            {
                Read(x);
                sol=BSearch(x);
                fout<<sol<<"\n";
            }
    }
    fin.close();
    fout.close();
    return 0;
}