//credite cezar pt 1% din cod
#include <fstream>
using namespace std;
int bit[10000002], x[10000002];
int n,m,c,q,p, ras;
void update(int i,int val)
{
    while(i<=n)
    {
        bit[i]+=val;
        i+=i&(-i);
    }
}
int calc(int i)
{
    int s=0;
    while(i>0)
    {
        s+=bit[i];
        i-=i&(-i);
    }
    return s;
}
int cautare(int b)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(calc(mij)<b)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st;
}
int main()
{
    ifstream cin("aib.in");
    ofstream cout("aib.out");
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        update(i,x[i]);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>c;
        if(c==0)
        {
            cin>>p>>q;
            update(p,q);
        }
        else if(c==1)
        {
            cin>>p>>q;
            ras=calc(q)-calc(p-1);
        }
        else
        {
            cin>>p;
            ras=cautare(p);
            if(calc(ras)!=p)
                ras=-1;
        }
        if(c>0)
            cout<<ras<<endl;

    }
    return 0;
}