#include <fstream>
#define ub(x) (x&(-x))
using namespace std;
int i,n,j,m,x,a,b,st,dr,mij,q,key,AIB[100001],k;
bool ok;
void add(int poz,int valoare)
{
    int i;
    for (i=poz;i<=n;i+=ub(i))
         AIB[i]+=valoare;

}
int sum(int poz)
{
    int s=0,i;
     for(i=poz;i>0;i-=ub(i))
        s+=AIB[i];
    return s;
}
int main()
{
    ifstream f("aib.in");
    ofstream g("aib.out");
    f>>n>>m;
    for(i=1;i<=n;i++) f>>x,add(i,x);
    for (i=1;i<=m;i++)
    {
        f>>key;key+=1;
        if (key==1)
            f>>j>>x,add(j,x);
        if (key==2)
            f>>a>>b,g<<sum(b)-sum(a-1)<<'\n';
        if (key==3)
            {
                f>>k;
                st=1;dr=n;ok=false;
                while (st<=dr&&!ok)
                   {
                       mij=(dr+st)/2;
                       q=sum(mij);
                       if (q==k) ok=true;
                          else if (q<k) st=mij+1;
                             else if (q>k) dr=mij-1;
                   }
                if (ok) g<<mij<<'\n';
                    else g<<"-1"<<'\n';
            }
    }
    f.close();
    g.close();
    return 0;
}