#include <iostream>
#include <fstream>
#define MAX 100000
#define nxt p-(p&(p-1))
#define up p&(p-1)

using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");

int aib[MAX+3];
int n,m;
int nr;

void updateT(int p, int nr) {
    while(p <= n) {
        aib[p] += nr;
        p += nxt;
    }
}

int sumT(int p) {
    int sum = 0;
    while(p != 0) {
        sum += aib[p];
        p = up;
    }
    return sum;
}

int searchT(int st, int dr, int s) {
    int mid = (st+dr)/2;
    int s2 = sumT(mid);
    if(st > dr)
        return -1;
    if(s2 < s)
        return searchT(mid+1, dr, s);
    if(s2 > s)
        return searchT(st, mid-1, s);
    return mid;
}

int main() {
    in >> n >> m;

    for(int i = 0; i < n; i++) {
        in >> nr;
        updateT(i+1, nr);
    }
    int t,a,b;
    for(int i = 0; i < m; i++) {
        in >> t;
        if(t == 0) {
            in >> a >> b;
            updateT(a, b);
        } else if(t == 1) {
            in >> a >> b;
            out << sumT(b)-sumT(a-1) << '\n';
        } else if(t == 2) {
            in >> a;
            out << searchT(0, n, a) << '\n';
        }
    }

    return 0;
}