#include<cstdio>
int v2[100001];
int main ()
{freopen ("aib.in","r",stdin);
freopen ("aib.out","w",stdout);
int n,m,i,j,c1,c2,x,k,q,s,c,a,b;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
    {scanf("%d",&b);
    a=i;
	while(a<=n)
		{v2[a]+=b;
		x=(a^(a&(a-1)));
		a+=x;
		}
    }
for(i=1;i<=m;i++)
    {scanf("%d",&c);
    if(c==0)
        {scanf("%d%d",&a,&b);
        while(a<=n)
            {v2[a]+=b;
            x=(a^(a&(a-1)));
            a+=x;
            }
        }
    if(c==1)
        {scanf("%d%d",&a,&b);
        a--;
        s=0;
        while(a>=1)
            {s+=v2[a];
            x=(a^(a&(a-1)));
            a-=x;
            }
        q=0;
        while(b>=1)
            {q+=v2[b];
            x=(b^(b&(b-1)));
            b-=x;
            }
        printf("%d\n",q-s);
        }
    if(c==2)
        {scanf("%d",&b);
        c1=1;
        c2=n;
        while(c1<=c2)
            {a=(c1+c2)/2;
            s=0;
            while(a>=1)
                {s+=v2[a];
                x=(a^(a&(a-1)));
                a-=x;
                }
            if(s==b)
                {printf("%d\n",(c1+c2)/2);
                c1=n+1;
                }
            else
                if(s<b)
                    c1=(c1+c2)/2+1;
                else
                    c2=(c1+c2)/2-1;
            }
        if(c1!=n+1)
            printf("-1\n");
        }
    }
return 0;
}