#include <bits/stdc++.h>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int aib[100010],n,m,i,j,x,val,poz,st,dr,mij,best,s,op,a,b,k;
void update(int val,int poz)
{
    for(int i=poz;i<=n;i=i+((i^(i-1))&i))
        aib[i]+=val;
}
int suma(int x)
{
    int s=0;
    for(int i=x;i>0;i=i-((i^(i-1))&i))
        s+=aib[i];
    return s;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        update(x,i);
    }
    for(i=1;i<=m;i++)
    {
        fin>>op;
        if(op==0)
        {
            fin>>poz>>val;
            update(val,poz);
        }
        if(op==1)
        {
            fin>>a>>b;
            fout<<suma(b)-suma(a-1)<<'\n';
        }
        if(op==2)
        {
            fin>>k;
            st=1;
            dr=n;
            best=-1;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                s=suma(mij);
                if(s==k)
                {
                    best=mij;
                    dr=mij-1;
                }
                else if(s<k)
                    st=mij+1;
                else dr=mij-1;
            }
            fout<<best<<'\n';
        }
    }
    return 0;
}