#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
const int N = 100010;
int n,aib[N],sum(int),lo,hi,mi,m,i,t,x,a,b;
void upd(int,int);

int main()
{
    f>>n>>m;
    for(i=1; i<=n; i++)
    {
        f>>x;
        upd(i,x);
    }
    for(; m; m--)
    {
        f>>t>>a;
        if(t==0)
        {
            f>>b;
            upd(a,b);
            continue;
        }
        if(t==1)
        {
            f>>b;
            g<<sum(b)-sum(a-1)<<'\n';
            continue;
        }
        for(lo=0,hi=n;hi-lo>1;)
        {
            mi=(lo+hi)/2;
            if(sum(mi)<a)
                lo=mi;
            else
                hi=mi;
        }
        if(sum(hi)!=a)hi=-1;
        g<<hi<<'\n';
    }
    return 0;
}
void upd(int p,int v)
{
    for(; p<=n; p+=p&(-p))
        aib[p]+=v;
}
int sum(int p)
{
    int v=0;
    for(; p; p-=p&(-p))
        v+=aib[p];
    return v;
}