#include <iostream>
#include <fstream>
#define zeros(x)((x^(x-1))&x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int aib[100001],N,M,x,y,z;
void ad(int poz,int val)
{
    for(int i=poz; i<=N; i+=zeros(i))
        aib[i]+=val;
}
int calc(int poz)
{
    int ret=0;
    for(int i=poz; i>0; i-=zeros(i))
        ret+=aib[i];
    return ret;
}
int poz_minim_suma(int k,int st,int dr)
{
    int mid=(st+dr)/2;
    int sum=calc(mid);
    if(st>dr)
        return -1;
    else
    {   if(k==sum)
           return mid;
        if(k<sum)
         return poz_minim_suma(k,st,mid-1);
        else return poz_minim_suma(k,mid+1,dr);

    }

}

int main()
{
    f>>N>>M;
    for(int i=1; i<=N; i++)
    {
        f>>x;
        ad(i,x);
    }
    for(int j=1; j<=M; j++)
    {
        f>>x;

        switch(x)
        {
        case(2):
            f>>y;
            g<<poz_minim_suma(y,1,N)<<'\n';
            break;
        case(1):
            f>>y>>z;
            g<<calc(z)-calc(y-1)<<'\n';
            break;
        case(0):
            f>>y>>z;
            ad(y,z);
            break;
        }

     }
    return 0;
}