#include <bits/stdc++.h>
 
using namespace std;

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

int getParent(int index) {
    return index - (index & -index);
}

int getNext(int index) {
    return index + (index & -index);
}

void updateTree(vector< int > &BIT, int value, int index) {
    while(index < (int)BIT.size()) {
        BIT[index] += value;
        index = getNext(index);
    }
}

int getSum(const vector< int >&BIT, int index) {
    int sum = 0;
    while(index > 0) {
        sum += BIT[index];
        index = getParent(index);
    }

    return sum;
}

vector< int > createTree(const vector< int > &v) {
    vector< int > BIT((int)v.size() + 1);

    for(int i = 1; i <= (int)v.size(); ++i) {
        updateTree(BIT, v[i - 1], i);
    }

    return BIT;
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    int n, m; in >> n >> m;

    vector< int > v(n);
    for(auto &it: v){
        in >> it;
    }

    vector< int > BIT = createTree(v);
    for(int i = 1; i <= m; ++i) {
        int type, a; in >> type >> a;

        if(type == 0) {
            int b; in >> b;
            updateTree(BIT, b, a);
        }
        if(type == 1) {
            int b; in >> b;
            out << getSum(BIT, b) - getSum(BIT, a - 1) << "\n";
        }
        if(type == 2) {
            int index = 1;
            while(index < (int)BIT.size()) {
                if(BIT[index] == a) {
                    out << index << "\n";
                    goto good;
                }
                index = getNext(index);
            }
            out << "-1\n";

            good:;
        }
    }
 
    in.close(); out.close();
 
    return 0;
}