#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,b;
long long a[100005];
void update(int p,int val)
{
    for(int i=p;i<=n;i+=(i&-i)) a[i]+=val;
}
long long sum(int p)
{
    long long s=0;
    for(int i=p;i>0;i-=(i&-i)) s+=a[i];
    return s;
}
int cb(int st,int dr,int x)
{
    if(st>dr) return -1;
    else
    {
        int m=(st+dr)/2;
        long long s=sum(m);
        if(s==x) return m;
        else if(s>x) return cb(st,m-1,x);
        else return cb(m+1,dr,x);
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i) {f>>b;update(i,b);}///25 42 8 15 1 55 16 67
    for(int i=1;i<=m;++i)
    {
        int c,y;
        f>>c>>y;
        if(c==0)
        {
            int x;
            f>>x;
            update(y,x);
        }
        else if(c==1)
        {
            int x;
            f>>x;
            g<<sum(x)-sum(y-1)<<'\n';
        }
        else g<<cb(1,n,y)<<'\n';
    }
    return 0;
}