#include <cstdio>
using namespace std;
int const N=100001;
int n,m,v[N];

int adun(int x,int val)
{
    while(x<=n)
    {
        v[x]+=val;
        x+=x&-x;
    }
}

int suma(int x)
{
    int sum=0;
    while(x!=0)
    {
        sum+=v[x];
        x -= x&-x;
    }
    return sum;
}

int caut(int x)
{
    int i=0, pas=1<<17;

    while(pas>0)
    {
         if(i+pas<=n)
         {
            if(x>=v[i+pas])
            {
                i+=pas;
                x-=v[i];
                if (x==0) return i;
            }
         }
         pas>>=1;
    }
    return -1;
}

int main()
{
    int i,tip,a,b,sdr,sst,x;
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        adun(i,x);
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d",&tip);
        if(tip==1 || tip==0) scanf("%d%d",&a,&b);
        else scanf("%d",&a);
        if(tip==0)
        {
            adun(a,b);
        }
        if(tip==1)
        {
            sdr=suma(b);
            sst=suma(a-1);
            printf("%d\n",sdr-sst);
        }
        if(tip==2)
        {
            printf("%d\n",caut(a));
        }
    }
    return 0;
}