#include <fstream>

using namespace std;
ifstream fin ("aib.in");
ofstream fout ("aib.out");
int c[100005], i, n, x, op, tip, a, b, k;
void adauga(int i, int x)
{
    int z=i, p;
    do
    {
        c[z]+=x;
        p=z&(z^(z-1));
        z+=p;
    }while(z<=n);
}
int suma(int a)
{
    int s=0, z=a, p;
    while(z>=1)
    {
        s+=c[z];
        p=z&(z^(z-1));
        z=z-p;
    }
    return s;
}
void raspuns(int k)
{
    int st=1, dr=n, mij, r=-1, s;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        s=suma(mij);
        if(s==k)
        {
            r=mij;
            dr=mij-1;
        }
        else if(s>k)
            dr=mij-1;
        else st=mij+1;
    }
    fout << r << '\n';
}
int main()
{
    fin >> n >> op;
    for(i=1;i<=n;i++)
    {
        fin >> x;
        adauga(i, x);
    }
    for(i=1;i<=op;i++)
    {
        fin >> tip;
        if(tip==0)
        {
            fin >> a >> b;
            adauga(a, b);
        }
        else if(tip==1)
        {
            fin >> a >> b;
            fout << suma(b)-suma(a-1)<< '\n';
        }
        else
        {
            fin >> k;
            raspuns(k);
        }
    }
    return 0;
}