#include <fstream>
using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");

int aib[100003],n,m;

int bit(int x)
{
    return (x&(x-1))^x;
}

void update(int x,int z)
{
    int i;
    for(i=x;i<=n;i+=bit(i))
    aib[i]+=z;
}

int sum(int x)
{
    int i,suma=0;
    for(i=x;i>0;i-=bit(i))
    suma+=aib[i];
    return suma;
}

int minp(int x)
{
    int step=1,i;
    for(;step<n;step<<=1);
    for(i=0;step;step>>=1)
    if(i+step<n&&x>=aib[i+step])
    {
        i+=step;
        x-=aib[i];
        if(!x)
        return i;
    }
    return -1;
}

int main()
{
    int i,x,op,y;
    in>>n>>m;
    for(i=1;i<=n;i++)
    in>>x,update(i,x);
    for(;m;--m)
    {
        in>>op;
        if(op==0)
        {
            in>>x>>y;
            update(x,y);
        }
        if(op==1)
        {
            in>>x>>y;
            out<<sum(y)-sum(x-1)<<'\n';
        }
        if(op==2)
        {
            in>>x;
            out<<minp(x)<<'\n';
        }
    }in.close(),out.close();
    return 0;
}