#include <bits/stdc++.h>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int v[100009], aib[100009], n, p[30];
void update (int poz, int add)
{
    for (int i=poz; i<=n; i+=i&-i)
        aib[i]+=add;
}
int querysum (int poz)
{
    int ans=0;
    for (int i=poz; i>=1; i-=i&-i)
        ans+=aib[i];
    return ans;
}
int querykth (int val)
{
    int poz=0;
    bool ok=0;
    int bit=20;
    while (bit>=0)
    {
        //cout <<bit<<'\n';
        while (bit>=0 && poz+p[bit]>n)
            bit--;
        if (aib[poz+p[bit]]==val)
            ok=1;
        if (aib[poz+p[bit]]<val)
            poz+=p[bit], val-=aib[poz];
        bit--;
    }
    if (ok)
        return poz+1;
    return -1;


}
signed main ()
{
    p[0]=1;
    for(int i=1; i<=20; i++)
        p[i]=2*p[i-1];
    int q;
    f >> n >> q;
    for (int i=1; i<=n; i++)
        f >> v[i], update (i, v[i]);
    while(q--)
    {
        int tip;
        f >> tip;
        if (tip==0)
        {
            int x, y;
            f >> x >> y;
            update (x, y);
        }
        if (tip==1)
        {
            int x, y;
            f >> x >> y;
            g << querysum (y)-querysum (x-1)<<'\n';
        }
        if (tip==2)
        {
            int x;
            f >> x;
            g << querykth(x)<<'\n';
        }
    }


}