#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("aib.in");
ofstream g ("aib.out");
int n,m;
int aib[100005], vek[100005];
void update(int x, int val)
{
    int i=x;
    int p=1;
    while(p<=n)
    {
        if(i%2==0) i++;
        if((i&(i-1))*p<x && i*p>=x)
            aib[i*p]+=val;
        i/=2;
        p*=2;
    }

}
int sum(int poz)
{
    int s=0,p=poz;
    while(p)
    {
        s+=aib[p];
        p=p&(p-1);
    }
    return s;

}
int gett(int k, int st, int dr)
{
    if(st==dr)
        return st;
    int mid=st+dr;
    mid/=2;
    if(sum(mid)>k)
    {
        gett(k, st, mid-1);
    }
    else if(sum(mid)<k)
    {
        gett(k, mid+1, dr);
    } else return mid;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        f>>vek[i];
        update(i, vek[i]);
    }
    for(int i=1;i<=m;++i)
    {
        int t,x,y;
        f>>t>>x;
        if(t!=2) f>>y;
        if(t==0)
        {
            update(x,y);
        } else if(t==1)
        {
           // g<<"h";
            g<<sum(y)-sum(x-1)<<"\n";
        } else
        {
            g<<gett(x,1,n)<<"\n";
        }
    }
    return 0;
}