#include <fstream>
using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");
const long long N=100000;
long long sum[N+1],n;
inline long long lsb(long long a)
{
    return a&-a;
}
void update(long long pos,long long val)
{
    for(; pos<=N; pos+=lsb(pos))
        sum[pos]+=val;
}
long long suma(long long pos)
{
    long long rez=0;
    for(; pos>0; pos-=lsb(pos))
        rez+=sum[pos];
    return rez;
}
long long cautbin(long long val)
{
    long long r=0,pas=1<<20;
    while(pas)
    {
        if(r+pas<=n&&val-sum[r+pas]>=0)
        {
            r+=pas;
            val-=sum[r];
        }
        pas/=2;
    }
    if(val==0)
    return r;
    return -1;
}
int main()
{
    long long q,i,sau,a,b,x;
    in>>n>>q;
    for(i=1; i<=n; i++)
    {
        in>>x;
        update(i,x);
    }
    for(i=1; i<=q; i++)
    {
        in>>sau>>a;
        if(sau!=2)
            in>>b;
        if(sau==0)
            update(a,b);
        else if(sau==1)
            out<<suma(b)-suma(a-1)<<'\n';
        else
            out<<cautbin(a)<<'\n';
    }
    return 0;
}