#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
#define NMAX 100000
int n,m,aib[NMAX+5],c,a,b,nr,poz,s;
int ub(int x)
{
    return (x & (-x));
}
void add(int x,int val)
{
    for(int i=x;i<=n;i+=ub(i))
    {
        aib[i]+=val;
    }
}
int sum(int x)
{
    int rez = 0;
    for(int i=x;i>=1;i-=ub(i))
    {
        rez+=aib[i];
    }
    return rez;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f>>c;
        add(i,c);
    }
    while(f>>c)
    {
        nr++;
        if(c==0)
        {
            f>>a>>b;
            add(a,b);
        }
        else if(c==1)
        {
            f>>a>>b;
            g<<sum(b)-sum(a-1)<<endl;
        }
        else if(c==2)
        {
            f>>a;
            poz = 0;
            s = 0;
            for(int i=17;i>=0;i--)
            {
                if(poz + (1<<i) <= n && s + aib[poz + (1<<i)] < a)
                {
                    s += aib[poz + (1<<i)];
                    poz += (1<<i);
                }
            }
            if(poz + 1 > n || sum(poz + 1) != a)
                g<<-1<<endl;
            else g<<poz+1<<endl;
        }
    }
    return 0;
}