#include <fstream>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int aib[100005],n,m;
void update(int poz,int x)
{
    for(;poz<=n;poz+=poz&(-poz))
        aib[poz]+=x;
}
int query(int poz)
{
    int s=0;
    for(;poz>0;poz-=poz&(-poz))
    {
        s=s+aib[poz];
    }
    return s;
}
int main()
{
    int i,a,b,c,x,ok;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        {
            fin>>x;
            update(i,x);
        }
    for(i=1;i<=m;i++)
    {
        fin>>a;
        if(a==0)
        {
            fin>>b>>c;
            update(b,c);
        }
        if(a==1)
        {
            fin>>b>>c;
            fout<<query(c)-query(b-1)<<"\n";
        }
        if(a==2)
        {
            fin>>b;
            int m,st,dr;
            dr=n;
            st=1;
            m=(n+1)/2;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(query(m)<b)
                    st=m+1;
                else
                {
                    if(query(m)>b)
                        dr=m-1;
                    else
                        if(query(m)==b)
                    {
                        ok=1;
                        break;
                    }
                }
            }
            if(ok==1)
                fout<<m<<"\n";
            else
                fout<<-1<<"\n";
        }
    }
    return 0;
}