#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n;
long long int x[100001];

void Update(int i, int v)
{while(i<=n)
 {x[i]+=v;
  i+=i&(-i);
 }
}

long long int Query(int a)
{long long int sol=0;
 while(a!=0)
 {sol+=x[a];
  a-=a&(-a);
 }
 return sol;
}

int Cauta(long long int a)
{int mij, st=1, dr=n;
 long long int b;
 while(st<=dr)
 {mij=(st+dr)/2;
  b=Query(mij);

  if(b==a)return mij;
  else if(b<a)st=mij+1;
  else dr=mij-1;
 }

 return -1;
}

int main()
{   int m, a, b, c;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {fin>>a;
     Update(i, a);
    }

    for(int i=1;i<=m;i++)
    {fin>>a>>b;
     if(a==0)
     {fin>>c;
      Update(b, c);
     }
     else if(a==1)
     {fin>>c;
      fout<<Query(c)-Query(b-1)<<"\n";
     }
     else fout<<Cauta(b)<<"\n";
    }

    return 0;
}