#include <fstream>
#define UB(x) (x&(-x))
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n,m,i,a,b,aib[100005],x,p;
void add(int x, int val)
{
    for(int i=x;i<=n;i+=UB(i))
        aib[i]+=val;
}
int sum(int x)
{
    int s=0;
    for(int i=x;i>0;i-=UB(i))
        s+=aib[i];
    return s;
}
int cb(int x)
{
    int st=1,dr=n,mij,s;
    while(st<=dr)
    {
        mij=(st+dr)>>1;
        s=sum(mij);
        if(x==s)
            return mij;
        if(x>s)
            st=mij+1;
        else
            dr=mij-1;
    }
    return -1;
}
int main()
{
   fin>>n>>m;
   for(i=1;i<=n;++i)
   {
       fin>>x;
       add(i,x);
   }
   for(i=1;i<=m;++i)
   {
       fin>>p>>a;
       if(p==0)
       {
           fin>>b;
           add(a,b);
       }
       else if(p==1)
       {
           fin>>b;
           fout<<sum(b)-sum(a-1)<<'\n';
       }
       else
       {
           fout<<cb(a)<<'\n';
       }
   }
    return 0;
}