#include <iostream>
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,aib[NMAX];
void adaugare(int val,int poz)
{
    for(int i=poz;i<=n;i+=(i&(-i)))
        aib[i]=aib[i]+val;
}
int facsuma(int poz)
{
    long long sum=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        sum=aib[i]+sum;
    return sum;
}
int cautare_binara(int x)
{
    int st=1, dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        int sum=facsuma(mij);
        if(sum==x)
            return mij;
        if(sum<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return -1;
}
void solve()
{
    f>>n>>m;
    int a,b,cerinta;
    for(int i=1;i<=n;i++)
    {   f>>a;
        adaugare(a,i);
    }
    for(int i=1;i<=m;i++)
    {
        f>>cerinta>>a;
        if(cerinta==0)
          {
              f>>b;
              adaugare(b,a);

          }
        else if(cerinta==1)
         {    f>>b;
             g<<facsuma(b)-facsuma(a-1)<<"\n";
         }
         else
         {
             g<<cautare_binara(a)<<'\n';
         }
    }


}

int main()
{
    solve();
    return 0;
}