#include <fstream>
using namespace std;
#define zeros(x) x&-x

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

int aib[100001], n, m;

void add(int x, int poz) {
    for(int i = poz; i <= n; i+= zeros(i))
        aib[i] += x;
}

int sum(int last) {
    int s = 0;
    for(int i = last; i > 0; i -= zeros(i))
        s += aib[i];
    return s;
}

int Search(int a) {
    int st = 1, dr = n;
    while(st <= dr) {
        int m = (st+dr)/2;
        int x = sum(m);
        if(x == a)
            return m;
        else if(x > a)
            dr = m-1;
        else
            st = m+1;
    }
    return -1;
}

int main() {
    f >> n >> m;
    int x;
    for(int i = 1; i <= n; i++) {
        f >> x;
        add(x, i);
    }
    for(int i = 1; i <= m; i++) {
        int op, a, b;
        f >> op;
        if(op == 0) {
            f >> a >> b;
            add(b, a);
        } else if(op == 1) {
            f >> a >> b;
            g << sum(b) - sum(a-1) << '\n';
        } else {
            f >> a;
            g << Search(a) << '\n';
        }
    }
}