#include <bits/stdc++.h>

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

long long n,m,i,a,b,cer,v[100001],x,poz,st,dr,mij,nr;

void update(int x, int val){
     for(int i=x;i<=n;i+=i&(-i))v[i]+=val;
}

int sum(int x){
     int s=0;
     for(int i=x;i>=1;i-=i&(-i))s+=v[i];
     return s;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++){
        f>>x;
        update(i,x);
    }
    for(i=1;i<=m;i++){
        f>>cer>>a;
        if(cer==0)
        {
            f>>b;
            update(a,b);
        }
        else if(cer==1){
            f>>b;
            g<<sum(b)-sum(a-1)<<'\n';
        }
        else if(cer==2){
            poz=0;
            st=1, dr=n;

            while(st<=dr && poz==0){
            mij=(st+dr)/2;
            nr=sum(mij);
            if(nr<a)st=mij+1;
            else if(nr>a)dr=mij-1;
            else if(nr==a)poz=mij;}

            if(poz==0)g<<-1<<'\n';
            else g<<poz<<'\n';
        }
    }
    return 0;
}