#include <cstdio>

using namespace std;

const int nmx = 100002;

int n,m,tree[nmx];

int pow2(int nr) {
    return nr & (-nr);
}

void update(int val, int pos) {
    while(pos <= n) {
        tree[pos] += val;
        pos += pow2(pos);
    }
}

int query(int pos) {
    int sum = 0;
    while(pos) {
        sum += tree[pos];
        pos -= pow2(pos);
    }
    return sum;
}

int _search(int val) {
    int left = 1, right = n;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        int this_val = query(mid);
        if(this_val == val)
            return mid;
        else if(this_val > val)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

void input() {
    scanf("%d %d", &n, &m);
    int val;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        update(val,i);
    }
}

int main() {
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);

    input();

    int a,b,c;

    for(int i = 1; i <= m; ++i) {
        scanf("%d", &c);
        if(c == 2) {
            scanf("%d", &a);
            printf("%d\n", _search(a));
        } else if(c == 1) {
            scanf("%d %d", &a, &b);
            printf("%d\n", query(b) - query(a-1));
        }
        else{
            scanf("%d %d", &a, &b);
            update(b,a);
        }
    }

    return 0;
}