#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>


using namespace std;
inline int lsb(int x) {
    return x & (-x);
}
int n,c[100007];
ifstream f("arbori.in");
ofstream g("arbori.out");

int m,p,q,a,x;
void aduna(int ind, int val)
{
    for(int i=ind; i<=n; i+=lsb(i))
        c[i]+=val;
}
int suma(int dr)
{
    int s=0;
   for(int i=dr; i>0; i-=lsb(i))
    s+=c[i];
    return s;


}
void caut(int i,int j,int x)
{
    if(x==suma((i+j)/2))
        g<<(i+j)/2<<"\n";
                else
            if(i<j)
            if(x<suma((i+j)/2) )
    caut(i,(i+j)/2 -1,x);
            else caut((i+j)/2+1,j,x);
                else g<<-1<<"\n";
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
        {
            f>>x;
            aduna(i,x);
        }
    for(int i=1; i<=m; i++)
    {
        f>>x;
        if(x==0)
            {
                f>>p>>q;
                aduna(p,q);
            }
        if(x==1)
        {
            f>>p>>q;
            g<<suma(q)-suma(p-1)<<"\n";
        }
        if(x==2)
        {
            f>>a;
            caut(1,n,a);
        }
    }
    return 0;
}