#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int tree[100001];
int n,m;


void update(int index, int value){
    while (index <= n){
        tree[index] += value;
        // add last '1'
        index = index + (index & -index);
    }
}

int read(int index){

    int sum = 0;
    while (index > 0){
        sum += tree[index];
        index = index - (index & -index);
    }

    return sum;
}

int binarySearch(int desiredSum, int left, int right){
    int middle = (left+right)/2;

    int middleValue = read(middle);

    if (desiredSum == middleValue){
        return middle;
    }
    else if (desiredSum < middleValue) {
        return binarySearch(desiredSum, left, middle-1);
    } else {
        return binarySearch(desiredSum, middle+1, right);
    }
}


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

    scanf("%d %d", &n, &m);

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

        update(i, val);
    }

    for (int i=0; i<m; i++){
        int op, a,b;
        scanf("%d %d", &op, &a);

        if (op != 2)
            scanf("%d", &b);

        int value, k;
        switch(op){
            case 0:
                update(a,b);
                break;
            case 1:
                value = read(b) - read(a-1);
                printf("%d\n", value);
                break;
            case 2:
                k = binarySearch(a, 1, n);
                printf("%d\n", k);
                break;

        }
    }


    return 0;
}