#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

int n, aib[100005], m, x;

int lsb(int x) { return -x&x; }

void update(int poz, int val)
{
    while (poz<=n)
        aib[poz]+=val, poz+=lsb(poz);
}

int query(int poz)
{
    int s=0;
    while (poz)
        s+=aib[poz], poz-=lsb(poz);
    return s;
}

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

    for (int ii=1; ii<=m; ++ii)
    {
        int tip, a, b; f>>tip;
        if (tip==0)
        {
            f>>a>>b; update(a, b);
        }
        if (tip==1)
        {
            f>>a>>b;
            g<<query(b)-query(a-1)<<'\n';
        }

        if (tip==2)
        {
            int q, ans=0; f>>x; q=x;
            for (int i=1<<16; i>0; i>>=1)
                if (i+ans<=n && aib[ans+i]<x)
                    x-=aib[ans+i], ans+=i;
            ++ans;
            if (ans!=-1 && query(ans)!=q) ans=-1;
            g<<ans<<'\n';
        }
    }

    return 0;
}