#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int F[100001], N;

void add(int p, int val){
    while(p<=N){
        F[p] += val;
        p += (p&(-p));
    }
}

int sum(int p){
    int rez;
    rez = 0;
    while( p >= 1 ){
        rez += F[p];
        p -= (p&(-p));
    }
    return rez;
}

int cb(int s, int d, int k){
    int m;
    while(s < d){
        m = s + (d - s) / 2;
        if( sum(m) == k ){
            d = m;
        }
        else if( sum(m) < k){
            s = m + 1;
        }
        else
            d = m - 1;
    }
    if( sum(s) == k )
        return s;
    else
        return -1;
}

int main()
{
    int a, b, m, v, i;
    f >> N >> m;
    for(i = 1; i <= N; i++){
        f >> a;
        add(i,a);
    }

    for(i = 1; i <= m; i++){
        f >> v;
        switch(v){
        case 0:
            f >> a >> b;
            add(a,b);
            break;
        case 1:
            f >> a >> b;
            g << sum(b) - sum(a-1) << '\n';
            break;
        case 2:
            f >> a;
            g << cb(1,N,a) << '\n';
            break;
        }
    }

    return 0;
}