#include <cstdio>

using namespace std;
#define Nmax 100005
int aib[Nmax],x,n,m;
void update( int poz,int x)
{
    aib[poz]+=x;
    int lsb=poz&(-poz);
    while(poz+lsb<=n){
        poz+=lsb;
        aib[poz]+=x;
        lsb=poz&(-poz);
    }
}
int query(int poz){
    int s=aib[poz];

    int lsb=poz&(-poz);
    while(poz-lsb>0){
        poz-=lsb;
        s+=aib[poz];
        lsb=poz&(-poz);
    }
    return s;
}
int search(int s){
    int p=1,u=n,mij;
    while(p<=u){
        mij=(p+u)/2;
        int rez=query(mij);
        if(s==rez) return mij;
        else
            if(s<rez)u=mij-1;
            else p=mij+1;
    }
    return -1;
}
int main()
{
    int op,a,b,x,y;
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
            scanf("%d",&x);
            update(i,x);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&op,&a);
            switch(op){
                case 0: scanf("%d",&b);
                        update(a,b);
                        break;
                case 1:scanf("%d",&b);
                        x=query(b);
                        y=query(a-1);
                        printf("%d\n",query(b)-query(a-1));
                        break;
                case 2:printf("%d\n",search(a));
                        break;
            }
        }
    return 0;
}