#include <fstream>
#define zeros(x) ((x^(x-1))&x)

using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");

int st,N,M,AIB[100002];

inline void adauga(int p,int val)
{
    for(;p<=N;p+=zeros(p))
        AIB[p]+=val;
}

inline int query(int p)
{
    int  s=0;
    for(;p>0;p-=zeros(p))
        s+=AIB[p];
    return s;
}

inline int BS(int c)
{
    int i,step;
    for(step=st,i=0;step>0;step>>=1)
    {
        if(i+step<=N&&c>=AIB[i+step])
            i+=step,c-=AIB[i];
        if(c==0)return i;
    }
}

int main()
{
    int c,i,p;
    in>>N>>M;
    for(i=1;i<=N;i++)in>>c,adauga(i,c);
    for(st=1;st<N;st<<=1);
    while(M--)
    {
        in>>i;
        if(i==0)
        {
            in>>p>>c;
            adauga(p,c);
        }
        if(i==1)
        {
            in>>p>>c;
            out<<query(c)-query(p-1)<<'\n';
        }
        if(i==2)
        {
            in>>c;
            out<<BS(c)<<'\n';
        }
    }
    return 0;
}