#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,q,a[100005],x,c,A,B;
void update(int x, int p)
{
    int i;
    for(i=p;i<=n;i+=i&(-i))
    {
        a[i]+=x;
    }
}
int suma(int p)
{
    int i,s=0;
    for(i=p;i>0;i-=i&(-i))
    {
        s+=a[i];
    }
    return s;
}
int caut_bin(int x)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(suma(mij)>x) dr=mij-1;
        else if(suma(mij)<x) st=mij+1;
        else return mij;
    }
    return -1;
}
int main()
{
    int i;
    f>>n>>q;
    for(i=1;i<=n;i++)
    {
        f>>x;
        update(x,i);
    }
    for(i=1;i<=q;i++)
    {
        f>>c;
        if(c==0)
        {
            f>>A>>B;
            update(B,A);
        }
        else if(c==1)
        {
            f>>A>>B;
            g<<suma(B)-suma(A-1)<<'\n';
        }
        else {f>>A;g<<caut_bin(A)<<'\n';}
    }
    return 0;
}