#include <fstream>
#define MAXN 1000005
#define zeros(x) ((x^(x-1))&x)
using namespace std;
long n, m;
unsigned long aib[MAXN];
void add(long x, unsigned long val)
{
    for(long i=x; i<=n; i+=zeros(i))
        aib[i]+=val;
}
unsigned long query(long x)
{
    unsigned long s=0;
    for(long i=x; i>0; i-=zeros(i))
        s+=aib[i];
    return s;
}
int main()
{
    ifstream in("aib.in");
    ofstream out("aib.out");
    unsigned long a, b, c, aux;
    bool stop;
    in>>n>>m;
    for(long i=1; i<=n; ++i)
    {
        in>>a;
        add(i, a);
    }
    for(long i=0; i<m; ++i)
    {
        in>>c;
        switch(c)
        {
        case 0:
            in>>a>>b;
            add(a, b);
            break;
        case 1:
            in>>a>>b;
            out<<query(b)-query(a-1)<<'\n';
            break;
        case 2:
            in>>a;
            b=1;
            while(b<n) b<<=1;
            c=b;
            c>>=1;
            stop=false;
            while(b&&c<=n&&!stop)
            {
                b>>=1;
                aux=query(c);
                if(aux>a) c-=b;
                else if(aux<a) c+=b;
                else
                {
                    out<<c<<'\n';
                    stop=true;
                }
            }
            if(!stop) out<<"-1\n";
            break;
        }
    }
    in.close(); out.close();
    return 0;
}