#include <bits/stdc++.h>

using namespace std;
long long int n,m,aint[100009],a,b,in2,sf2;
ifstream f("aib.in");
ofstream g("aib.out");
///-------------------------------------------
void update(int in, int sf, int nod, int val, int poz)
{
    if(in==sf)
    {
        aint[nod]+=val;
        return;
    }
    int mij=(in+sf)/2;
    if(poz<=mij)
    {
        update(in, mij, 2*nod, val, poz);
    }
    else update(mij+1, sf, 2*nod+1, val, poz);
    aint[nod]=aint[2*nod]+aint[2*nod+1];
}
///-------------------------------------------
int cauta1(int in, int sf, int in2, int sf2, int nod)
{
    if(in==in2 && sf==sf2)
        return aint[nod];
    int mij=(in+sf)/2;
    if(mij<in2)
    {
        return cauta1(mij+1,sf,in2, sf2, 2*nod+1);
    }
    if(mij>=sf2)
    {
        return cauta1(in,mij,in2,sf2,2*nod);
    }
    if(mij>=in2 && mij<sf2)
    {
        return cauta1(mij+1,sf,mij+1, sf2, 2*nod+1)+cauta1(in,mij,in2,mij,2*nod);
    }

}
///-------------------------------------------
int cauta2(int in, int sf, int nod, int a)
{
    if(in==sf && a==aint[nod]) return in;
    else if(in==sf) return -1;
    int mij=(in+sf)/2;
    if(aint[2*nod]>=a) return cauta2(in, mij, nod*2, a);
    else return cauta2(mij+1, sf, nod*2+1, a-aint[nod*2]);
}
///-------------------------------------------
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        f>>x;
        ///in,sf,nod,val,poz
        update(1,n,1,x,i);
    }
    for(int i=1;i<=m;i++)
    {
        int c;
        f>>c;
        if(c==0)
        {
            f>>a>>b;
            update(1,n,1,b,a);
        }
        if(c==1)
        {
            f>>in2>>sf2;
            g<<cauta1(1,n,in2,sf2,1)<<"\n";
        }
        if(c==2)
        {
            f>>a;
            ///in,sf,nod,totatl
            g<<cauta2(1,n,1,a)<<"\n";
        }
    }
    return 0;
}