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