#include <fstream>
#include <vector>
using namespace std;
 
#define in "aib.in"
#define out "aib.out"
#define N 100005
 
vector <int> aib (N, 0);
int n, m;
 
void add (int i, int v) {
    while (i <= n) {
        aib[i] += v;
        i += (i^(i-1)) & i;
    }
}
 
int query (int i) {
    int s = 0;
    while (i > 0) {
        s += aib[i];
        i -= (i^(i-1)) & i;
    }
    return s;
}
 
int BS (int x) {
    int lo = 1, hi = n+1;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        int val = query (mid);
        if (val == x)
            return mid;
        else
            if (val < x)
                lo = mid + 1;
        else
            hi = mid;
    }
    return -1;
}
 
int main () {
    ifstream fin (in);
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)  {
        int x;
        fin >> x;
        add (i, x);
    }
    ofstream fout (out);
    for (int i = 0; i < m; ++i) {
        int type;
        fin >> type;
        if (!type) {
            int a, b;
            fin >> a >> b;
            add (a, b);
        }
        else
            if (type == 1) {
                int a, b;
                fin >> a >> b;
                fout << query (b) - query (a-1) << "\n";
            }
        else {
            int x;
            fin >> x;
            fout << BS (x) << "\n";
        }
    }
    fcloseall();
    return 0;
}