#include<cstdio>
#include<cctype>
#define aib_SIZE 100000
using namespace std;

int aib[aib_SIZE+1], n, m;

inline void updateAIB(int poz, int x) {
    while(poz <= n) {
        aib[poz] += x;
        poz += poz & (-poz);
    }
}

inline int sumQuery(int poz) {
    int sum = 0;
    while(poz) {
        sum += aib[poz];
        poz &= (poz-1);
    }
    return sum;
}

int binarySearch(int x) {
    int st, dr, mij, poz, val;
    st = 1, dr = n, poz = -1;
    while(st <= dr && poz == -1) {
        mij = (st + dr) >> 1;
        val = sumQuery(mij);
        if(x == val)
            poz = mij;
        else if(x < val)
            dr = mij - 1;
        else st = mij + 1;
    }
    return poz;
}

int main() {
    int a, b, op, i, x;
    FILE* fin, *fout;
    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",&x);
        updateAIB(i,x);
    }
    for(i = 1; i <= m; i++) {
        fscanf(fin,"%d%d",&op,&a);
        if(op != 2)
            fscanf(fin,"%d",&b);
        if(!op)
            updateAIB(a,b);
        else if(op == 1)
            fprintf(fout,"%d\n",sumQuery(b)-sumQuery(a-1));
        else fprintf(fout,"%d\n",binarySearch(a));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}