#include <fstream>
using namespace std;

const int N=100005;
int v[N],n;

ifstream in("aib.in");
ofstream out("aib.out");

void next_up(int& x)
{
    x=2*x-(x&(x-1));
}

void next_q(int& x)
{
    x&=x-1;
}

void update(int x,int val)
{
    for (;x<=n;next_up(x))
        v[x]+=val;
}

int query(int x)
{
    if (!x)
        return 0;
    int val=0;
    for (;x;next_q(x))
        val+=v[x];
    return val;
}

int bs(int x)
{
    int i,step=1<<16;
    for (i=0;step;step>>=1)
        if (i+step<=n && v[i+step]<=x)
        {
            i+=step;
            x-=v[i];
        }
    return !x ? i : -1;
}

int main()
{
    int q,x,y;
    in>>n>>q;
    for (int i=1;i<=n;i++)
    {
        in>>x;
        update(i,x);
    }
    while (q--)
    {
        in>>x;
        if (x==1)
        {
            in>>x>>y;
            update(x,y);
            continue;
        }
        if (x==2)
        {
            in>>x>>y;
            out<<query(y)-query(x-1)<<"\n";
            continue;
        }
        in>>x;
        out<<bs(x)<<"\n";
    }
    return 0;
}