#include <fstream>

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

constexpr int N = 1e5+1;

namespace aib{
    int v[N];

    int g(int i){
        return i & (-i);
    }
    
    void point_update(int i, int val, int n){
        for(; i <= n; i += g(i)){
            v[i] += val;
        }
    }

    int sum(int i){
        int res = 0;
        while(i > 0){
            res += v[i];
            i -= g(i);
        }
        return res;
    }

    int range_query(int a, int b){
        return sum(b) - sum(a-1);
    }
};

int cbin(int val, int n){
    int st=1, dr=n, mij;
    while(st < dr){
        mij = (st + dr) / 2;
        if(aib::sum(mij) >= val) dr = mij;
        else st = mij + 1;
    }
    return (aib::sum(st) == val ? st : -1);
}

int main(){
    int n, m;
    in >> n >> m;
    for(int i=1; i<=n; ++i){
        int x;
        in >> x;
        aib::point_update(i, x, n);
    }
    for(int i=0; i<m; ++i){
        int op, a, b;
        in >> op;
        switch (op){
        case 0:
            in >> a >> b;
            aib::point_update(a, b, n);
            break;
        
        case 1:
            in >> a >> b;
            out << aib::range_query(a, b) << '\n';
            break;

        default:
            in >> a;
            out << cbin(a, n) << '\n';
            break;
        }
    }
}