#include <stdio.h>
#define MAXBUF 8192
#define MAX 100000

using namespace std;

int n,m;
int nr;
char buf[MAXBUF];
char buf2[3000000];
int cntR = MAXBUF;
int cntW = 0;
int aib[MAX+3];
FILE *fin;

bool isdigit(char ch) {
    return (ch >= '0' && ch <= '9');
}

char nextch() {
    if(cntR == MAXBUF) {
        fread(buf, 1, MAXBUF, fin);
        cntR = 0;
    }
    return buf[cntR++];
}

int read() {
    int val = 0;
    char ch = nextch();
    while(!isdigit(ch))
        ch = nextch();
    while(isdigit(ch)) {
        val = val*10 + ch - '0';
        ch = nextch();
    }
    return val;
}

void updateT(int p, int nr) {
    while(p <= n) {
        aib[p] += nr;
        p += p-(p&(p-1));
    }
}
int sumT(int p) {
    int sum = 0;
    while(p != 0) {
        sum += aib[p];
        p = p&(p-1);
    }
    return sum;
}
int searchT(int st, int dr, int s) {
    if(st > dr)
        return -1;
    int mid = st+((dr-st)/2);
    int s2 = sumT(mid);
    if(s2 < s)
        return searchT(mid+1, dr, s);
    if(s2 > s)
        return searchT(st, mid-1, s);
    return mid;
}

int main() {

    fin = fopen("aib.in", "r");
    FILE *fout = fopen("aib.out", "w");

    //fscanf(fin, "%d %d", &n, &m);
    n = read();
    m = read();

    for(int i = 0; i < n; i++) {
        //fscanf(fin, "%d", &nr);
        nr = read();
        updateT(i+1, nr);
    }
    int t,a,b;
    for(int i = 0; i < m; i++) {
        //fscanf(fin, "%d", &t);
        t = read();
        if(t == 0) {
            //fscanf(fin, "%d %d", &a, &b);
            a = read();
            b = read();
            updateT(a, b);
        } else if(t == 1) {
            //fscanf(fin, "%d %d", &a, &b);
            a = read();
            b = read();
            fprintf(fout, "%d\n", sumT(b)-sumT(a-1));
        } else if(t == 2) {
            //fscanf(fin, "%d", &a);
            a = read();
            fprintf(fout, "%d\n", searchT(1, n, a));
        }
    }

    return 0;
}