#include <iostream>
#include <fstream>

#define zeros(x) ((x^(x-1))&x)
#define nmax 100000

using namespace std;

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

int aib[nmax], n;

void Add(int x, int val)
{
    for(int i=x; i<=n; i+=zeros(i))
    {
        aib[i]+=val;
    }
}

int Compute(int x)
{
    int sum=0;
    for(int i=x; i>=1; i-=zeros(i))
    {
        sum+=aib[i];
    }
    return sum;
}

int minim(int a, int b)
{
    if(a<b) return a;
    else return b;
}

int Search(int a)
{
    int st=0, dr=n+1;
    int b, s;
    int pos=n+1;
    b=n;
    s=Compute(n);
    if(s==a) pos=n;
    while(b>0)
    {
        b=(st+dr)/2;
        s=Compute(b);
        if(s>a)
        {
            if(dr>b) dr=b;
            --b;
        }
        else
        {
            if(s==a)
            {
                pos=(minim(pos, b));
                dr=b--;
            }
            else
            {
                if(st<b) st=b;
                ++b;
            }
        }
        if(dr<=b || st>=b) break;
    }
    if(pos==n+1) return -1;
    else return pos;
}

int main()
{
    int m;
    int p, a, b;
    f>>n>>m;
    for(int i=1; i<=n; ++i)
    {
        f>>a;
        Add(i, a);
    }
    for(int i=1; i<=m; ++i)
    {
        f>>p;
        if(p==0)
        {
            f>>a>>b;
            Add(a, b);
        }
        if(p==1)
        {
            f>>a>>b;
            g<<Compute(b)-Compute(a-1)<<"\n";
        }
        if(p==2)
        {
            f>>a;
            g<<Search(a)<<"\n";
        }
    }
    return 0;
}