#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int n_max = 100005;

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

int aib[n_max];
int n, m;

void update (int poz, int val) {
    while (poz <= n) {
        aib[poz] += val;
        poz += poz & (-poz);
    }
}

int querry (int poz) {
    int sum = 0;
    while (poz) {
        sum += aib[poz];
        poz -= poz & (-poz);
    }
    return sum;
}

int search_aib (int k) {
    int s = querry(n), lo = 0, hi = n + 1, pos = n + 1, div;
    if (s == k) pos = n;

    while (div) {
        div = (lo + hi) / 2;
        s = querry(div);

        if (s > k) {
            if (hi > div) hi = div;
            div--;
        }
        else if (s == k) pos = min(pos,div), hi = div, div--;
        else {
            if (lo<div) lo = div;
            div++;
        }
        if (lo >= div) break;
        if (hi <= div) break;
    }

    if ( pos == n+1 ) return -1;
    return pos;
}

int main()
{

    fin >> n >> m;

    for (int i=1; i<=n; i++) {
        int x;
        fin >> x;
        update(i, x);
    }

    for (int i=1; i<=m; i++) {
        int op;
        fin >> op;
        if (op == 0) {
            int a, b;
            fin >> a >> b;
            update(a,b);
        }
        else if (op == 1) {
            int a, b;
            fin >> a >> b;
            fout << querry(b) - querry(a-1) << '\n';
        }
        else {
            int a;
            fin >> a;
            fout << search_aib(a) << '\n';
        }
    }

    return 0;
}