#include "fstream"
#include "vector"
#include "queue"

using namespace std;

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

const int INF = 1000000005;
const int NMAX = 100005;

int N, M;

int aib[NMAX];

void add(int x, int pos) {
//    fout << "In add function" << "\n";
//    fout.flush();
    int powOf2 = 2;

    while(pos % powOf2 == 0) {
//        fout << "pos: " << pos << '\n';
//        fout << "powOf2: " << powOf2 << '\n';
//        fout.flush();
        powOf2 *= 2;
    }

    do{
//        fout << "pos is: " << pos << "\n";
//        fout << "aib[pos] is: " << aib[pos] << "\n";
        aib[pos] += x;
//        fout << "aib[pos] is: " << aib[pos] << "\n";
        pos += powOf2 - (pos % powOf2);
        powOf2 *= 2;
    }while(pos <= N);

}

int sum(int pos) {

    if(pos == 0) {
        return 0;
    }

    int result = 0;
    int pow = 1;
    while(pow * 2 <= pos) {
        pow *= 2;
    }

    int location = pow;
    while(pow) {
        result += aib[location];
        while(location + pow > pos) {
            pow /= 2;
        }
        location += pow;
    }
    return result;
}

int search(int value) {
    int pow = 1;
    while(pow * 2 <= N) {
        pow *= 2;
    }

    int location = 0;
    while(pow) {
        while(location + pow > N || sum(location + pow) >= value) {
            pow /= 2;
        }
        location += pow;
    }

    location++;
//    fout << "location is: " << location << "\n";

    if(sum(location) == value) {
        return location;
    }
    return -1;
}

int main() {

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

//    fout << "Read all numbers";
//    for(int i = 1 ; i <= N ; i++) {
//        fout << aib[i] << " ";
//    }
//    fout << "\n";

    for(int i = 1 ; i <= M ; i++) {
        int type;
        fin >> type;
        if(type == 0) {
            int pos, val;
            fin >> pos >> val;
            add(val, pos);

//            fout << "Read all numbers";
//            for(int i = 1 ; i <= N ; i++) {
//                fout << aib[i] << " ";
//            }
//            fout << "\n";
        }
        else if(type == 1) {
            int start, end;
            fin >> start >> end;
            fout << sum(end) - sum(start - 1) << "\n";
        }
        else {
            int value;
            fin >> value;
            fout << search(value) << "\n";
        }
    }
}