#include <cstdio>

using namespace std;

int aib[1000010],n;

int query(int p) {
    int rez=0,pow2;
    while (p!=0) {
        rez+=aib[p];
        pow2=(p&(-p));
        p-=pow2;
    }
    return rez;
}

void update(int p,int val) {
    int pow2;
    while (p<=n) {
        aib[p]+=val;
        pow2=(p&(-p));
        p+=pow2;
    }
}

int search1(int val) {
    int i=0,pas=1<<16;
    while (pas!=0) {
        if (i+pas<=n && aib[i+pas]<=val) {
            i+=pas;
            val-=aib[i];
        }
        pas/=2;
    }
    if (val==0)
        return i;
    else
        return -1;
}

int main()
{
    FILE *fin,*fout;
    int m,i,a,t,b;
    fin=fopen("aib.in","r");
    fout=fopen("aib.out","w");
    fscanf(fin,"%d%d", &n, &m);
    for (i=1;i<=n;i++) {
        fscanf(fin,"%d", &a);
        update(i,a);
    }
    for (i=1;i<=m;i++) {
        fscanf(fin,"%d%d", &t, &a);
        if (t<2)
            fscanf(fin,"%d", &b);
        if (t==0)
            update(a,b);
        if (t==1)
            fprintf(fout,"%d\n", query(b)-query(a-1));
        if (t==2)
            fprintf(fout,"%d\n", search1(a));
    }
    return 0;
}