#include <bits/stdc++.h>
#define step(x) ((x^(x-1))&x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

int arb[100005],i,tip,n,m,nr,poz,val,st,dr;

void update (int poz , int val)
{
    int h;
    for (h=poz;h<=n;h+=step(h))
      arb[h]+=val;
}

int query (int poz)
{
    int h,sol=0;
    for (h=poz;h>=1;h-=step(h))
     sol+=arb[h];
    return sol;
}

int bin_search (int val)
{
    int mij,st=1,dr=n;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (query(mij)==val)
         return mij;
        if (query(mij)<val)
         st=mij+1;
        else
         dr=mij-1;
    }
}

int main()
{
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        f>>nr;
        update(i,nr);
    }
    for (i=1;i<=m;i++)
    {
        f>>tip;
        if (tip==0)
        {
            f>>poz>>val;
            update(poz,val);
        }
        if (tip==1)
        {
            f>>st>>dr;
            g<<(query(dr)-query(st-1))<<'\n';
        }
        if (tip==2)
        {
            f>>val;
            g<<bin_search(val)<<'\n';
        }
    }
    return 0;
}