#include <stdio.h>

using namespace std;

int c,n,op,arb[100100];

void insert(int poz, int val) {
    int put=0;
    while (poz<n) {
        arb[poz]+=val;
        while((poz & (1<<put)) == 0) put++;
        poz+=(1<<put);
        put=put+1;
    }
}

int query(int poz) {
    int sum=0, put=0;
    while (poz>0) {
        sum+=arb[poz];
        while((poz & (1<<put)) == 0) put++;
        poz-=(1<<put);
        put++;
    }
    return sum;
}

int cautare(int val) {
    int put = 1, i=0;
    while (put < n) put=put<<1;
    while (put > 0) {
        if(i+put < n)
            if(val >= arb[i+put]) {
                i+=put;
                val-=arb[i];
                if(val == 0) return i;
            }
        put>>=1;
    }
    return -1;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d %d",&n,&c);
    int tp,nr,poz,st,dr,val;
    for(int i=1;i<=n;i++) {
        scanf("%d",&nr);
        insert(i, nr);
    }
    for(int i=1; i<=c;i++) {
        scanf("%d",&tp);
        if(tp==0) {
            scanf("%d %d",&poz,&nr);
            insert(nr, poz);
        }
        else if(tp==1) {
            scanf("%d %d",&st,&dr);
            printf("%d\n",query(dr)-query(st-1));
        }
        else if(tp==2) {
            scanf("%d",&val);
            printf("%d\n",cautare(val));
        }
    }
    return 0;
}