#include<stdio.h>
int a,t[100100],op,x,y,N,M;

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

void add(int x, int y) {
    int curr = x;
    while(curr <= N) {
        t[curr] += y;
        curr += right(curr);
    }
}

int sum(int x) {
    int curr = x, rez = 0;
    while(curr) {
        rez += t[curr];
        curr -= right(curr);
    }
    return rez;
}

int caut(int x) {
    int st=1,dr=N;
    while(st<=dr) {
        int mij = (st+dr)/2;
        int val = sum(mij);
        if(val==x) {
            return mij;
        } else if(val<x) {
            st = mij+1;
        } else {
            dr = mij-1;
        }
    }
    return -1;
}

int main() {
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i) {
        scanf("%d",&a);
        add(i,a);
    }
    for(int i=1;i<=M;++i) {
        scanf("%d",&op);
        if(op==0) {
            scanf("%d%d",&x,&y);
            add(x,y);
        } else if(op==1) {
            scanf("%d%d",&x,&y);
            printf("%d\n",sum(y)-sum(x-1));
        } else {
            scanf("%d",&x);
            printf("%d\n",caut(x));
        }
    }
}