#include <fstream>
#include <cstdlib>

using namespace std;

const int N_MAX=100011;

int aib[N_MAX];

inline int log2(int x) { return 8*sizeof(int)-__builtin_clz(x)-1; }
void Update(const int& N, int xIndex, const int& xValue)
{
    for(; xIndex <= N; xIndex+=(xIndex & -xIndex) )
        aib[xIndex]+=xValue;
}
int Sum(int xIndex)
{
    int s;

    for(s=0; xIndex; xIndex-=(xIndex & -xIndex) )
        s+=aib[xIndex];

    return s;
}
int Search(const int& N, int k)
{
    int index, tIndex=0, tidx=0;
    for(index=1<<log2(N); index; index>>=1)
    {
        tidx=tIndex+index;
        if(tidx <= N)
        {
            if(k < aib[tidx])
                continue;
            if(k == aib[tidx])
                return tidx;
            k-=aib[tidx];
            tIndex=tidx;
        }
    }
    return -1;
}
int main()
{
    int N, M, x, i, op, a, b;
    ifstream in( "aib.in");
    ofstream out("aib.out");

    in>>N>>M;
    for(i=1; i <= N; ++i)
    {
        in>>x;
        Update(N, i, x);
    }
    for(; M; --M)
    {
        in>>op>>a;
        if(0 == op)
           in>>b, Update(N, a, b);
        else if(1 == op)
                in>>b, out<<(Sum(b)-Sum(a-1))<<'\n';
              else out<<Search(N, a)<<'\n';
    }
    return EXIT_SUCCESS;
}