#include <fstream>

using namespace std;
ifstream fin ("aib.in");
ofstream fout ("aib.out");
int v[100001],i,op,poz,val,n,m,x,y;
void adunare(int val, int poz)
{
    int i,z;
    i=poz;
    do
    {
        v[i]+=val;
        z=i&(i^(i-1));
        i+=z;
    }
    while(i<=n);
}
int sum(int poz)
{
    int i,z;
    long long sum=0;
    i=poz;
    do
    {
        sum+=v[i];
        z=i&(i^(i-1));
        i-=z;
    }
    while(i>=1);
    return sum;
}
int bs(int val)
{
    int mij,st=1,dr=n;
    long long suma;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        suma=sum(mij);
        if(suma==val)
            return mij;
        if(suma>val)
            dr=mij-1;
        else
            st=mij+1;
    }
    return -1;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        adunare(x, i);
    }
    for(i=1;i<=m;i++)
    {
        fin>>op;
        if(op==0)
        {
            fin>>poz>>val;
            adunare(val, poz);
        }
        if(op==1)
        {
            fin>>x>>y;
            fout<<sum(y)-sum(x-1)<<'\n';
        }
        if(op==2)
        {
            fin>>val;
            fout<<bs(val)<<'\n';
        }
    }
    return 0;
}