#include <bits/stdc++.h>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
const int nmax=100001;
int a[nmax],n,query;
inline void Update_Op1(int p,int x)
{
    while(p<=n)
    {
        a[p]+=x;
        p+=(p&(-p));
    }
}
inline int Query(int p)
{
    int suma=0;
    while(p>=1)
    {
        suma+=a[p];
        p-=(p&(-p));
    }
    return suma;
}
inline int CautBin_Op2(int x)
{
    int st=1,dr=n,mij,poz=-1,suma;
    while(st<=dr)
    {
        mij=(dr-st)/2+st;
        suma=Query(mij);
        if(suma==x)
        {
            poz=mij;
            dr=mij-1;
        }
        else if(x>suma)
            st=mij+1;
        else dr=mij-1;
    }
    return poz;
}
inline void Read_Solve()
{
    int i,x,y,op;
    fin>>n>>query;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        Update_Op1(i,x);
    }
    for(i=1;i<=query;i++)
    {
        fin>>op;
        if(op==0)
        {
            fin>>x>>y;
            Update_Op1(x,y);
        }
        else if(op==1)
        {
            fin>>x>>y;
            fout<<Query(y)-Query(x-1)<<"\n";
        }
        else
        {
            fin>>x;
            y=CautBin_Op2(x);
            fout<<y<<"\n";
        }
    }
}
int main()
{
    Read_Solve();
    fin.close();
    fout.close();
    return 0;
}