#include <bits/stdc++.h>
#define Nmax 100005

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int a[Nmax];
int n, m;

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

}

int query (int poz){
    int sum = 0;
    while (poz > 0){
        sum += a[poz];
        poz -= (poz&(-poz));
    }
    return sum;
}

int caut_bin (int k){
    int l = 1, r = n, mid, val;
    while (l <= r){
        mid=(l+r)/2;
        val = query (mid);
        if(val == k) return mid;
        if(val < k) l=mid+1;
        else r=mid-1;
    }
    return -1;
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; i++){
        int x;
        f >> x;
        update (i, x);
    }
    int op, x, y, k;
    for(int i = 1; i <= m; i++){
        f >> op;
        if (op == 0){
            f >> x >> y;
            update (x, y);
        } else {
            if(op == 1){
                f >> x >> y;
                g << query(y) - query(x - 1) << '\n';
            } else {
                f >> k;
                g << caut_bin(k) << '\n';
            }
        }
    }

    return 0;
}