#include <cstdio>
#include <cstring>
#define nmax 100010
#include <algorithm>
#include <assert.h>
#define xmax 2147483648

using namespace std;

int tree[nmax];
int n,m;

void read();
void update(int,int);
void print();
int query(int);
int search(int);

int main(){
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    memset(tree,0,sizeof(tree));
    read();
    print();
    return 0;
}

void read(){
    scanf("%d %d ",&n,&m);
    assert(1 <= n && n <= nmax - 10);
    assert(1 <= m && m <= 150000);
    int x;
    for(int i = 1;i <= n;i++){
        scanf("%d ",&x);
        update(i,x);
    }
}

void update(int pos,int val){
    int c = 0;
    while(pos <= n){
        tree[pos] += val;
        while(!(pos & (1<<c)))c++;
        pos += (1<<c);
        c++;
    }
}

void print(){
    int k,x,y;
    while(m--){
        scanf("%d ",&k);
        switch(k){
        case 0:
            scanf("%d %d ",&x,&y);
            assert(1 <= x && x <= n);
            assert(1 <= y && y <= 10000);
            update(x,y);
            break;
        case 1:
            scanf("%d %d ",&x,&y);
            assert(1 <= x && x <= y && y <= n);
            printf("%d\n",query(y) - query(x-1));
            break;
        case 2:
            scanf("%d ",&x);
            assert(1 <= x && x <= xmax);
            printf("%d\n",search(x));
        }
    }
}

int query(int pos){
   int c = 0,s = 0;
    while(pos > 0){
        s += tree[pos];
        while(!(pos & (1<<c)))c++;
        pos -= (1<<c);
        c++;
    }
    return s;
}

int search(int sum){
    int pos = n + 1,b = n;
    int limst = 0,limdr = n + 1;
    int s = query(b);
    if(s == sum)pos = n;
    while(b){
        b = (limst + limdr)>>1;
        s = query(b);
        if(s < sum){
            if(limst < b)limst = b;
            b++;
        }
        else if(s == sum){
            pos = min(pos,b);
            limdr = b;
            b--;
        }
        else{
            if(limdr > b){
                limdr = b;
                b--;
            }
        }
        if(b <= limst)break;
        if(b >= limdr)break;
    }
    if(pos == n + 1)return -1;
    return pos;
}