#include<cstdio>
#define NMAX 100001
using namespace std;
int aib[NMAX],n;
inline  void update(int val, int poz)
{
    for(; poz<=n; poz+=poz&(poz-1)^poz)
        aib[poz]+=val;
}
inline int query(int day2)
{
    int s=0,i;
    for(i=day2; i; i-=i&(-i))
        s+=aib[i];
    return s;
}
int binarysearch(int left,int right, int val)
{
    int mid,prev;
    while(left<=right)
    {
        mid =(left+right)>>1;
        int ask=query(mid);
        {
            if(ask<=val)
            {
                prev=ask;
                left=mid+1;
                if(prev==val)
                    return mid;
            }
            else
                right=mid-1;
        }

    }
return -1;
}
/*int searching(int k)
{
    int sol,sc;
    sol=sc=0;
    for(int step=1<<17; step>0; step>>=1)
        if(sol+step<=n&&sc+aib[sol+step]<=k)
        {
            sol+=step;
            sc+=aib[sol];

        }
    if(sc!=k||sol==0)
        return -1;
    return sol;
} */
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int m,i,sum,operation,day1,day2;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; ++i)
    {
        scanf("%d",&sum);
        update(sum,i);
    }
    for(i=1; i<=m; ++i)
    {
        scanf("%d",&operation);
        switch(operation)
        {
        case 0 :
            scanf("%d%d",&day1,&sum);
            update(sum,day1);
            break;
        case 1 :
            scanf("%d%d",&day1,&day2);
            printf("%d\n",query(day2)-query(day1-1));
            break;
        case 2 :
            scanf("%d",&sum);
            printf("%d\n",binarysearch(1,n,sum));
            break;
        }
    }



    return 0;
}