#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
unsigned int AIB[100001],i,a,b,n,m,caz;
unsigned int zeros(int x)
{
    return ((x^(x-1))&x);
}
void bagval(unsigned int poz,unsigned int val)
{
    while(poz<=n)
    {
        AIB[poz]+=val;
        poz+=zeros(poz);
    }
}
unsigned int Query(unsigned int poz)
{
    unsigned int suma=0;
    while(poz)
    {
        suma+=AIB[poz];
        poz-=zeros(poz);
    }
    return suma;
}
unsigned int cauta(unsigned int val,unsigned int step=0)
{
    for (step = 1; step <= n; step <<= 1);//2 la k
    step >>= 1;
    for (i=0; step; step >>= 1)
    {
        if (step <= n)
        {
            if(AIB[step]<=val)
            {
                i += step;
                val -= AIB[i];
                if (!val) return i;
            }
        }
    }
    return -1;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++) {f>>a; bagval(i,a);}
    while(m--)
    {
        f>>caz;
        if(!caz) {f>>a>>b; bagval(a,b);}
        else if(caz==1) {f>>a>>b; g<<Query(b)-Query(a-1)<<'\n';}
        else {f>>a; g<<cauta(a)<<'\n';}
    }
    g.close();
    return 0;
}