#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;

long long aib[NMAX];

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

    do{

        while(pos % powOf2 == 0) {
//        fout << "pos: " << pos << '\n';
//        fout << "powOf2: " << powOf2 << '\n';
//        fout.flush();
            powOf2 *= 2;
        }
//        fout << "pos is: " << pos << "\n";
//        fout << "aib[pos] is: " << aib[pos] << "\n";
//        fout << "adding: " << originalPos << " to " << pos << "\n";
        aib[pos] += x;
//        fout << "aib[pos] is: " << aib[pos] << "\n";
        pos += powOf2 - (pos % powOf2);
        powOf2 *= 2;
    }while(pos <= N);

}

long long sum(long long pos) {

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

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

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

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

    long long location = 0;
    long long sum = 0;
    while(pow) {
        while((location + pow > N || sum + aib[location + pow] > value) && pow) {
//            fout << "not taken sum: " << sum + aib[location + pow] << "\n";
//            fout << "not taken location: " << location + pow << "\n";
//            fout.flush();
            pow /= 2;
        }
        if(pow) {
            sum += aib[location + pow];
            location += pow;
//            fout << "sum: " << sum << "\n";
//            fout << "location: " << location << "\n";
//            fout.flush();
            pow /= 2;
        }
    }

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

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

int main() {

    fin >> N >> M;
    for(int i = 1 ; i <= N ; i++) {
        long long 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++) {
        long long type;
        fin >> type;
        if(type == 0) {
            long long 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) {
            long long start, end;
            fin >> start >> end;
            fout << sum(end) - sum(start - 1) << "\n";
        }
        else {
            long long value;
            fin >> value;
            fout << search(value) << "\n";
        }
    }
}