#include <fstream>
#define in "aib.in"
#define out "aib.out"
#define N 100003
#define zerouri(x) ((x^(x-1))&x)

using namespace std;

ifstream fin(in);
ofstream fout(out);

int A[N];
int n,m,x,y,p;
int pos,val;

inline void adauga()
{
    while(pos <= n)
    {
        A[pos] += val;
        pos += zerouri(pos);
    }
}

inline int suma(int E)
{
    if(E == 0) return 0;
    return A[E] + suma(E-zerouri(E));
}

inline int poz_minim(int S)
{
    int st,dr,mij,sum;
    st = 1,dr = n;

    while(st<=dr)
    {
        mij = (st+dr)/2;
        sum = suma(mij);
        if(sum == S) return mij;
        else if(sum < S)
            st = mij + 1;
        else
            dr = mij - 1;
    }

    return -1;
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; ++i)
    {
        fin>>val;
        pos = i;
        adauga();
    }

    while(m--)
    {
        fin>>p;
        if(p == 0)
        {
            fin>>pos>>val;
            adauga();
        }
        else if(p == 1)
        {
            fin>>x>>y;
            fout<<suma(y) - suma(x-1)<<"\n";
        }
        else
        {
            fin>>x;
            fout<<poz_minim(x)<<"\n";
        }
    }

    fin.close(); fout.close();
    return 0;
}