#include <fstream>
#define zero(x) x&(-x)
using namespace std;
ifstream f ("aib.in");
ofstream g ("aib.out");
const int NMax = 100002;
int n,m,x,p,a,b,AIB[NMax];
void update(int ind,int v)
{
    for(int i=ind;i<=n;i+=zero(i)) AIB[i]+=v;
}
int sum(int x)
{
    int s=0;
    for(int i=x;i>=1;i-=zero(i)) s+=AIB[i];
    return s;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        f>>x;
        update(i,x);
    }
    for(int i=1;i<=m;++i)
    {
        f>>p;
        if(p==0)
        {
            f>>a>>b;
            update(a,b);
        }
        if(p==1)
        {
            f>>a>>b;
            g<<sum(b)-sum(a-1)<<'\n';
        }
        if(p==2)
        {
            f>>a;
            int mid,st=1,dr=n,ok=0;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(sum(mid)==a)
                {
                    g<<mid<<'\n';
                    ok=1;
                    break;
                }
                else if(sum(mid)<a) st=mid+1;
                else if(sum(mid)>a) dr=mid-1;
            }
            if(ok==0) g<<-1<<'\n';
        }
    }
    return 0;
}