#include <fstream>
#define DIM 100010
using namespace std;

int a[DIM];
int n, x, p, q, k, i, t, op;

int lsb(int x) {
    return x&-x;
}

void update(int i, int x) {
    for (;i<=n;i+=lsb(i))
        a[i]+=x;
}

int query(int i) {
    int s = 0;
    for (;i!=0;i-=lsb(i))
        s+=a[i];
    return s;
}

int query2(int k) {
    int st = 1; int dr = n, mid;
    while (st <= dr) {
        mid = st + (dr-st)/2;
        if (query(mid) >= k) {
            dr = mid-1;
        } else {
            st = mid+1;
        }
    }
    if (query(st) != k)
        return -1;
    return st;
}

int main() {
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin>>n>>t;
    for (i=1;i<=n;i++) {
        fin>>x;
        update(i, x);
    }

    for (;t;t--) {
        fin>>op;
        if (op == 0) {
            fin>>p>>x;
            update(p,x);
        } else
            if (op == 1) {
                fin>>p>>q;
                fout<<query(q) - query(p-1)<<"\n";
            } else {
                fin>>k;
                fout<<query2(k)<<"\n";
            }
    }

    return 0;
}