#include <fstream>

using namespace std;

const int MAX_N = 100002;

int N, M;
int A[MAX_N];

void update(int pos, int val) {
    for( ; pos <= N; pos += pos ^ (pos & (pos - 1)))
        A[pos] += val;
}

int query(int pos) {
    int ret = 0;

    for( ; pos > 0; pos -= pos ^ (pos & (pos - 1)))
        ret += A[pos];
    
    return ret;
}

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

    f >> N >> M;
    for(int i = 1, x; i <= N; ++i) {
        f >> x;

        update(i, x);
    }
    
    for(int i = 1, t, x, y; i <= M; ++i) {
        f >> t;
            
        if(t == 0) {
            f >> x >> y;
            
            update(x, y);
        }
        else if(t == 1) {
            f >> x >> y;

            g << query(y) - query(x - 1) << "\n";
        }
        else {
            f >> x;

            int sol = -1;
            for(int l = 1, r = N, m = 0; l <= r; ) {
                m = (l + r) / 2;
                
                int sum = query(m);

                if(sum < x)
                    l = m + 1;
                else {
                    if(sum == x)
                        sol = m;
                    r = m - 1;
                }    
            }

            g << sol << "\n";

        }
    }

    f.close();
    g.close();

    return 0;
}