#include <stdio.h>
#include <vector>

using namespace std;

vector<int> tree;
int n;

inline int get_level() {
    int level;
    for(level = 1; (1<<level) < n; ++level);
    return level;
}

int next_child(int ancestor, int x, bool restart = false) {
    static int level = 0;

    if (restart) {
        level = get_level() - 1;
        return 1;
    }

    int child = 1;
    if ((x - 1) & (1<<level))
        child = 2 * ancestor + 1;
    else
        child = 2 * ancestor;

    --level;
    return child;
}

void update(int i, int val) {
    int pos = next_child(0, 0, true);
    while(pos < n*2) {
        tree[pos] += val;
        pos = next_child(pos, i);
    }
}

int running_sum(int sum) {
    int pos = 1, current_numbers, total_numbers = 0;
    
    current_numbers = 1 << get_level();

    while(pos < 2*n) {
        if (sum == tree[pos])
            return current_numbers > n ? n : total_numbers + current_numbers;

        if (sum < tree[pos]) {
            current_numbers = current_numbers / 2;
            pos = pos * 2;
        }
        else {
            sum -= tree[pos];
            total_numbers += current_numbers;
            pos = pos + 1;
        }

    }

    return -1;
}

int sum_to(int x) {
    int pos = 1, up_to = 0, current_leaves;
    int sum = 0;
    current_leaves = n;
    
    current_leaves = 1 << get_level();

    if (x < 1)
        return 0;

    while(pos < 2 * n)  {
        current_leaves = current_leaves / 2;
        if (current_leaves < 1) {
            sum += tree[pos];
            break;
        }

        if (x <= up_to + current_leaves) {
            pos = pos * 2;
        } else {
            pos = pos * 2 + 1;
            up_to += current_leaves;
            sum += tree[pos - 1];
        }
    };

    return sum;
}

int interval_sum(int x, int y) {
    return sum_to(y) - sum_to(x-1);
}


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

    int m, val, x, y, type;
    
    scanf("%d%d", &n, &m);
    tree.assign(1 << get_level() + 1, 0);

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

    for(int i=1; i<=m; ++i) {
        scanf("%d", &type);

        switch(type) {
            case 0:
                scanf("%d%d", &x, &val);
                update(x, val);
                break;
            
            case 1:
                scanf("%d%d", &x, &y);
                printf("%d\n", interval_sum(x, y));
                break;

            case 2:
                scanf("%d", &x);
                printf("%d\n", running_sum(x));
                break;
        }
    }

    return 0;
}