#include <fstream>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int arb[100010];
int n, m, op, a, b, x;

void update(int poz, int val)
{
    for(poz; poz<=n; poz+=(-poz)&poz)
        arb[poz]+=val;
}

int sum(int p)
{
    int s=0;
    for(; p>0; p-=(-p)&p)
        s+=arb[p];
    return s;
}

int cauta(int p)
{
    int i,step;
    for(step=1;step<n;step<<=1);
    for(i=0;step>0;step>>=1)
    {
        if(i+step<=n)
        {
            if(p>=arb[step+i])
            {
                i+=step;p-=arb[i];
                if(p==0)return i;
            }
        }
    }
    return -1;
}

int main()
{

    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        fin>>x;
        update(i, x);
    }

    while(m--)
    {
        fin>>op;
        switch(op)
        {
        case 0:
            fin>>a>>b;
            update(a,b);
            break;
        case 1:
            fin>>a>>b;
            fout<<sum(b)-sum(a-1)<<'\n';
            break;
        case 2:
            fin>>a;
            fout<<cauta(a)<<'\n';
            break;
        }
    }
    return 0;
}