#include<fstream>
#define AIB_SIZE 100000
using namespace std;

class AIB {
private:
    int aib[AIB_SIZE + 1], aibSize;
public:
    void updateAIB(int val, int pos) {
        while(pos <= aibSize) {
            aib[pos] += val;
            pos += pos & (-pos);
        }
    }

    int querySum(int x) {
        int sum = 0;
        while(x) {
            sum += aib[x];
            x &= (x - 1);
        }
        return sum;
    }

    int binarySearch(int a) {
        int left, right, mid, pos, val;
        left = 1, right = aibSize, pos = -1;
        while(left <= right && pos == -1) {
            mid = (left + right) >> 1;
            val = querySum(mid);
            if(val == a)
                pos = mid;
            else if(a > val)
                left = mid + 1;
            else right = mid - 1;
        }
        return pos;
    }

    void readArray(string name_fin, string name_fout) {
        int op, a, b, m, i;
        ifstream fin(name_fin);
        ofstream fout(name_fout);
        fin >> aibSize >> m;
        for(i = 1; i <= aibSize; i++) {
            fin >> a;
            updateAIB(a, i);
        }
        for(i = 1; i <= m; i++) {
            fin >> op >> a;
            if(op != 2)
                fin >> b;
            if(op == 0)
                updateAIB(b, a);
            else if(op == 1)
                fout << querySum(b) - querySum(a - 1) << "\n";
            else fout << binarySearch(a) << "\n";
        }
        fin.close();
        fout.close();
    }
};

int main() {
    AIB aib;
    aib.readArray("aib.in", "aib.out");
    return 0;
}