#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define min(a,b) (a<b?a:b)
int *aib,n,x,r;
void upd(int i,int a){
    i++;
    while(i<=n){
        aib[i]+=a;
        i+=(i&(-i));
    };
};
int get(int i){
    int sum=0;
    i++;
    while(i>0){
        sum+=aib[i];
        i-=(i&(-i));
    };
    return sum;
};
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&n,&r);
    aib=(int *)calloc(n,sizeof(int));
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        upd(i,x);
    }
    int a,b,c;
    for(int i=0;i<r;i++){
        scanf("%d%d",&c,&a);
        if(c!=2) scanf("%d",&b);
        if(c==0){
            upd(a-1,b);
        }
        else if(c==1){
            printf("%d\n",get(b-1)-get(a-2));
        }
        else{
            int l=0,d=n,sol=INT_MAX;
            while(l<d){
                int m=(l+d)/2;
                if(get(m)>a){
                    d=m;
                }
                else if(get(m)<a){
                    l=m+1;
                }
                else{
                    sol=min(m,sol);
                    break;
                }
            }
            printf("%d\n",sol+1);
        }
    }
    return 0;
}