#include <cstdio>

using namespace std;

int n, m;
int sir[100005];

int put2(int x){
    return ((x ^ (x - 1)) & x);
}

void update(int x, int y){
    for(int i = x; i <= n; i += put2(i)){
        sir[i] += y;
    }
}

int querry(int x){
    int sum = 0;

    for(int i = x; i > 0; i -= put2(i)){
        sum += sir[i];
    }

    return sum;
}

void citire(){
    scanf("%d %d", &n, &m);
    int x;

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

int binarySearch(int x){
    int st = 1;
    int dr = n;

    while(st < dr){
        int m = (st + dr) / 2;
        int y = querry(m);

        if(y > x){
            dr = m - 1;
        }
        else if(y < x){
            st = m + 1;
        }
        else if(y == x){
            dr = m;
        }
    }

    if(querry(st) != x){
        return -1;
    }
    return st;
}

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

    citire();

    for(int k = 0; k < m; k++){
        int p, x, y;

        scanf("%d", &p);

        if(p == 0){
            scanf("%d %d", &x, &y);
            update(x, y);
        }
        else if(p == 1){
            scanf("%d %d", &x, &y);
            printf("%d\n", querry(y) - querry(x - 1));
        }
        else if(p == 2){
            scanf("%d", &x);
            printf("%d\n", binarySearch(x));
        }
    }

    return 0;
}