#include<cstdio>
#define NMAX 100000+5
using namespace std;
int AIB[NMAX];
int N,M;
void add(int i,int x)
{
    for(;i<=N;i+=i&(-i)) AIB[i]+=x;
}
int query(int i)
{
    int s=0;
    for(;i;i-=i&(-i)) s+=AIB[i];
    return s;
}
int binary_search(int x)
{
    int st=1,dr=N,md,s;
    for(;st<=dr;)
    {
        md=(st+dr)/2;
        s=query(md);
        if(s<x) {st=md+1; continue;}
        if(s>x) {dr=md-1; continue;}
        return md;
    }
    return -1;
}
int main()
{
    int i,x,a,b;
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++)
    {
        scanf("%d",&x);
        add(i,x);
    }
    for(;M;--M)
    {
        scanf("%d",&x);
        if(x==0)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            continue;
        }
        if(x==1)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",query(b)-query(a-1));
            continue;
        }
        scanf("%d",&a);
        printf("%d\n",binary_search(a));
    }
    return 0;
}