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

int n, aib[100005], m;

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

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

inline 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)
    {
        int x; f>>x;
        update(x, i);
    }

    for (int i=1; i<=m; ++i)
    {
        int tip, a, b; f>>tip;
        if (tip==0)
            f>>a>>b, update(b, a);

        if (tip==1) g<<query(b)-query(a-1)<<'\n';

        if (tip==2)
        {
            int x, q, ans=0; q=x; f>>x;
            for (int i=1<<16; i; 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;
}