#include <bits/stdc++.h>

using namespace std;
int values[100001], arb[100001];

int mub(int n){
    return (n & (-n));
    // returns 2^(mub(i))
}

int query (int i){
    if (i == 0) {
        return 0;
    }
    else{
        return arb[i] + query(i- mub(i));
    }
}

int binarySearch(int x, int n){
    int position = 0;
    for (int power = 20; power >= 0 ; power --){
        if (position  + (1 << power) <= n && (arb[position + (1 << power)] < x or (arb[position + (1 << power)] == x and (power == 0 or arb[position + (1 << power - 1)] != x)))){
            position += (1 << power);
            x -= arb[position];
        }
    }
    return position;
}

void update(int position, int n, int value){
    while(position <= n){
        arb[position] += value;
        position += mub(position);
    }
}

int main() {
    ifstream f ("aib.in");
    ofstream g ("aib.out");
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= n; i++){
        f >> values[i];
        update(i, n, values[i]);
    }
    for (int i = 1; i <= m; i ++){
        int op;
        f >> op;
        if (op == 0){
            int a, b;
            f >> a >> b;
            update(a, n, b);
        }
        if (op == 1){
            int a, b;
            f >> a >> b;
            int sum = 0;
            sum = query(b) - query(a - 1);
            g << sum << "\n";
        }
        if (op == 2){
            int a, k = 0;
            f >> a;
            k = binarySearch(a, n);
            if (k == 0) g << -1 << "\n";
            else g << k << "\n";
        }
    }
    return 0;
}