#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("aib.in");
ofstream h("aib.out");
int n,m,a[100002],t,k,j,l;
void add(int i,int q)
{
    for(;i<=n;i=i+((i^(i-1))&i)){a[i]+=q;}
}
int aic(int i)
{
    int s=0;
    for(;i>0;i=i-((i^(i-1))&i))s+=a[i];
    return s;
}
int src(int q)
{
    int p=1;
    while(p<n)p*=2;
    for(int i=0;p>0;p/=2)
    {
        if(i+p<=n)
        {
            if(q>=a[i+p])
            {
                i+=p;q-=a[i];
                if(q==0)return i;
            }
        }
    }
    return -1;
}
int main()
{
    //freopen("aib.in","r",stdin);
    //freopen("aib.out","w",stdout);
    //scanf("%d%d",&n,&m);
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        //scanf("%d",&t);
        f>>t;
        add(i,t);
    }
    for(int g=1;g<=m;++g)
    {
        //scanf("%d",&k);
        f>>k;
        switch(k)
        {
        case 0:
            //scanf("%d%d",&k,&t);
            f>>k>>t;
            add(k,t);
            break;
        case 1:
            //scanf("%d%d",&k,&t);
            f>>k>>t;
            //printf("%d\n",aic(t)-aic(k-1));
            h<<aic(t)-aic(k-1)<<'\n';
            break;
        case 2:
            //scanf("%d",&k);
            f>>k;
            //printf("%d\n",src(k));
            h<<src(k)<<'\n';
            break;
        }
    }
}