#include <iostream>
#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int v[100001],n;
void adaug(int x,int p)
{
    for(; p<=n; p+=((p^(p-1))&p))
    {
        v[p]+=x;
    }
}
int querry(int x)
{
    int ans=0;
    for(; x>0; x-=((x^(x-1))&x))
    {
        ans+=v[x];
    }
    return ans;
}
int cautbinar(int x)
{
    int p=1,u=n,m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(querry(m)<x) p=m+1;
        else if(querry(m)>x) u=m-1;
        else return m;
    }
    return -1;
}
int main()
{
    int i,x,q,a,b,m,j;
    f>>n>>m;
    for(i=1; i<=n; i++)
    {
        f>>x;
        adaug(x,i);
    }

    for(i=1; i<=m; i++)
    {
        f>>q;
        if(q==0)
        {
            f>>j>>x;
            adaug(x,j);
        }
        else if(q==1)
        {
            f>>a>>b;
            //cout<<querry(b)<<" "<<querry(a-1)<<'\n';
            g<<querry(b)-querry(a-1)<<'\n';
        }
        else
        {
            f>>x;
            g<<cautbinar(x)<<'\n';
                    }
    }

    return 0;
}