#include <iostream>
#include <cstdio>
#define fin "aib.in"
#define fou "aib.out"
#define Max 100010
using namespace std;
int n,m,aib[Max];

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

void update(int pos,int val)
{
    int i;
    for(i=pos;i<=n;i+=zeros(i)) aib[i]+=val;
}

int query(int poz)
{
    int i,rez=0;
    for(i=poz;i>=1;i-=zeros(i)) rez+=aib[i];
    return rez;
}

int getpos(int val)
{
    int k=0,poz=1;
    while(poz<n) poz<<=1;
    while(poz>0)
    {
        if(k+poz<=n)
            if(aib[k+poz]<=val)
            {
                val-=aib[k+poz];
                k+=poz;
                if(val==0) return k;
            }
        poz>>=1;
    }
    return -1;
}

int main()
{
    int i,x;
    freopen(fin,"r",stdin);
    freopen(fou,"w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        update(i,x);
    }
    int cod,a,b;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&cod,&a);
        if(cod!=2) scanf("%d",&b);
        if(cod==0) update(a,b);
        if(cod==1) printf("%d\n",query(b)-query(a-1));
        if(cod==2) printf("%d\n",getpos(a));
    }
    fclose(stdout);
    fclose(stdin);
    return 0;
}