#include <stdio.h>
#include <iostream>
#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++];
}

void putW(int nr) {
    if(nr < 0) {
        buf2[cntW++] = '-';
        buf2[cntW++] = '1';
        buf2[cntW++] = '\n';
        return;
    }
    int st = cntW;
    while(nr > 0) {
        buf2[cntW++] = nr%10 + '0';
        nr /= 10;
    }
    int ln = cntW-st;
    for(int i = 0; i < ln/2; i++) {
        char aux = buf2[cntW-ln+i];
        buf2[cntW-ln+i] = buf2[cntW-i-1];
        buf2[cntW-i-1] = aux;
    }
    buf2[cntW++] = '\n';
}

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");

    n = read();
    m = read();

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

    return 0;
}