#include <bits/stdc++.h>

using namespace std;

#define TREE_MAX 100005

struct AibNode {
    int value;
    AibNode* prevVersion;

    AibNode() {
        value = 0;
        prevVersion = 0;
    }
};

struct AibTree {
    AibNode *tree[TREE_MAX];
    int size;
    int zero(int x) { return (x ^ (x - 1)) & x; }

    AibTree(int size) {
        this->size = size;

        for(int i = 1; i <= size; i++) {
            tree[i] = new AibNode;
        }
    }

    void update(int position, int value) {
        for(int i = position; i <= size; i += zero(i)) {
           AibNode* newNode = new AibNode;
           newNode->value = tree[i]->value + value;
           newNode->prevVersion = tree[i];
           tree[i] = newNode;
        }
    }

    int query(int position) {
        int result = 0;
        for(int i = position; i > 0; i -= zero(i)) {
            result += tree[i]->value;
        }
        return result;
    }

};

int binSearch(AibTree& tree, int k)
{
    int left = 1, right = tree.size;

    while(left <= right) {
        int middle = (left + right) >> 1;
        int sum = tree.query(middle);
        if(sum == k)
            return middle;
        if(sum > k) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }

    return -1;
}

int numberOfItems, numberOfQueries;

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

    scanf("%d %d ", &numberOfItems, &numberOfQueries);

    AibTree tree(numberOfItems);

    for(int i = 1; i <= numberOfItems; i++) {
        int item;
        scanf("%d ", &item);
        tree.update(i, item);
    }

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

        if(queryType == 0) {
            int position, value;
            scanf("%d %d ", &position, &value);
            tree.update(position, value);
        }
        else if(queryType == 1) {
            int start, finish;
            scanf("%d %d ", &start, &finish);
            printf("%d\n", tree.query(finish) - tree.query(start - 1));
        }
        else if(queryType == 2) {
            int k;
            scanf("%d ", &k);
            printf("%d\n", binSearch(tree, k));
        }
    }

    return 0;
}