#include <fstream>
#define zeros(x) x&-x
using namespace std;

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

int n,m,aib[100010];

void push(int i,int x)
{
    for(;i<=n;i+=zeros(i))
        aib[i]+=x;
}
int query(int i)
{
    int rez=0;
    for(;i>0;i-=zeros(i))
        rez+=aib[i];
    return rez;
}

void citire()
{
    f>>n>>m;
    int a;
    for(int i=1;i<=n;i++)
    {
        f>>a;
        push(i,a);
    }
}

int search(int a, int b, int val)
{
    int m=(a+b)/2;
    int v=query(m);
    if(v==val)
        return m;
    if(a>=b)
      return -1;
    else
        if(val>v)
            return search(m+1,b,val);
        else
            return search(a,m-1,val);
}
int fct(int i)
{
    if(!i)
        return -1;
    return i;
}
int main()
{
    citire();
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        f>>c;
        if(!c)
        {
            f>>a>>b;
            push(a,b);
        }
        else
            if(c==1)
            {
                f>>a>>b;
                g<<query(b)-query(a-1)<<'\n';
            }
            else
            {
                f>>a;
                g<<fct(search(1,n,a))<<'\n';
            }
    }
    return 0;
}