#include <cstdio>

using namespace std;

int aib[100005],n;
void update(int poz,int x) {
    for(; poz<=n; poz+=(poz&(-poz)))
        aib[poz]+=x;
}
int query(int poz) {
    int s=0;
    for(; poz>0; poz-=(poz&(-poz)))
        s+=aib[poz];
    return s;
}
int main() {
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int m,i,x,a,b,st,dr,med;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; ++i) {
        scanf("%d",&x);
        update(i,x);
    }
    for(i=1; i<=m; ++i) {
        scanf("%d",&x);
        if(!x) {
            scanf("%d%d",&a,&b);
            update(a,b);
        } else {
            if(x==1) {
                scanf("%d%d",&a,&b);
                printf("%d\n",query(b)-query(a-1));
            } else {
                scanf("%d",&a);
                st=1;
                dr=n;
                while(st<=dr) {
                    med=(st+dr)/2;
                    if(query(med)==a) {
                        break;
                    } else if(query(med)<a)
                        st=med+1;
                    else
                        dr=med-1;
                }
                printf("%d\n",med);
            }
        }
    }
    return 0;
}