#include <iostream>
#include<cstdio>
using namespace std;
int aib[100001], /*n2[100001],*/n;
int putdoi(int);
void update(int nr, int i)
{
    while(i<=n)
    {
        aib[i]+=nr;
        i+=putdoi(i);
    }
}
int putdoi(int n)
{
    int i=1;
    while(n%2==0)
    {
        n/=2;
        i*=2;
    }
    return i;
}
int query(int n)
{
    int sum=0;
    while(n>0)
    {
        sum+=aib[n];
        n-=putdoi(n);
    }
    return sum;
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int m, i,nr, c, a,sum,b;
    scanf("%d%d", &n, &m);
    //for(i=1;i<=n;i++)
     //   n2[i]=putdoi(i);
    for(i=1;i<=n;i++)
    {
        scanf("%d", &nr);
        update(nr, i);
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d", &c);
        if(c==0)
        {
            scanf("%d%d", &a, &b);
            nr=a;
            while(nr<=n)
            {
                aib[nr]+=b;
                nr+=putdoi(nr);
            }
        }
        if(c==1)
        {
            scanf("%d%d", &a, &b);
            printf("%d\n", query(b)-query(a-1));
        }
        if(c==2)
        {
            scanf("%d", &sum);
            int l1=1, l2=n,gasit=0,mij;
            while(l1<=l2&&gasit==0)
            {
                mij=(l1+l2)/2;
                a=query(mij);
                if(sum==a){
                    gasit=1;
                    printf("%d\n", mij);
                    break;
                }
                if(a<sum)
                    l1=mij+1;
                if(a>sum)
                    l2=mij-1;
            }
            if(gasit==0)
                printf("-1\n");
        }
    }
    return 0;
}