#import<fstream>
int N,o,t,x,y,B['썐'],s,i,z;

int U(int p){for(;N/p;p+=p&-p)B[p]+=x;}

int Q(int p){for(s=0;p;p&=~-p)s+=B[p];return s;}

int main(){

    std::ifstream f("aib.in");
    std::ofstream g("aib.out");

    for(f>>N>>o;N/++y;U(y))f>>x;

    for(;o--;)
    {
        f>>t>>y;

        s=1;

        for(x=y;N/s;s*=2)z=-1;

        for(i=0;s;s/=2) (i + s > N || x < B[i + s]) || ((x -= B[i += s]) || (z = i, s = 0));

        t<2&&f>>x;

        t?g<<(t&1?Q(x)-Q(y-1):z)<<'\n',0:U(y);
    }
}