#include <iostream>
#include <fstream>

std::ifstream in("aib.in");
std::ofstream out("aib.out");

const int N=100000;

int AIB[N+2];

void update(int poz, int dif, int n)
{
    int casuta=poz+1;
    while(casuta<=n+1)
    {
        AIB[casuta]+=dif;
        casuta=casuta+(casuta&-casuta);
    }
}

int sum(int poz)
{
    int s=0;

    int casuta=poz+1;
    while(casuta!=0)
    {
        s+=AIB[casuta];
        casuta=casuta-(casuta&-casuta);
    }

    return s;
}

int interogare(int suma, int n)
{
    int st=1, dr=n+1, mij;

    while(st+1!=dr)
    {
        mij=(st+dr)/2;

        if(sum(mij)<suma)
        {
            st=mij+1;
        }
        else
        {
            dr=mij;
        }
    }

    if(sum(st)!=suma) return -1;

    return st;
}

int main()
{
    int n, m, x, l, r, b;

    in>>n>>m;
    for(int i=1; i<=n; ++i)
    {
        in>>x;
        update(i, x, n);
    }

    for(int i=1; i<=m; ++i)
    {
        in>>x;

        if(x==0)
        {
            in>>l>>r;
            update(l, r, n);
            continue;
        }

        if(x==1)
        {
            in>>l>>r;
            out<<sum(r)-sum(l-1)<<"\n";
            continue;
        }

        if(x==2)
        {
            in>>b;
            out<<interogare(b, n)<<"\n";
            continue;
        }
    }

    return 0;
}