#include<fstream>
using namespace std;

int L=18,aib[10000002],n,m;

int interogare(int p)
{
    int s=0;
    while(p!=0)
    {
        s+=aib[p];
        p-=(p&(-p));
    }
    return s;
}

void actualizare(int p, int val)
{
    while(p<=n)
    {
        aib[p]+=val;
        p+=p&(-p);
    }
}
int caut(int x)
{
    int p=0, pas=1<<L;
    while(pas!=0)
    {
        if(p+pas<=n && aib[p+pas]<=x)
        {
            p+=pas;
            x-=aib[p];
        }
        pas/=2;
    }
    if(x!=0)
    {
        return -1;
    }
    return p;
}

int main()
{
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    ios::sync_with_stdio(false);
    int tip,t;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>t;
        actualizare(i,t);
    }
    for(int i = 1; i <= m; i++)
    {
        fin>>tip;
      if( tip == 0 ) {
        int a, b;
        fin>>a>>b;
        actualizare(a, b);
      }
      else if( tip == 1 ) {
        int a,b;
        fin>>a>>b;
        fout<<interogare(b) - interogare(a - 1)<<'\n';
      }
      else {
        int a;
        fin>>a;
        fout<<caut(a)<<'\n';
      }
    }

    fin.close();
    fout.close();

    return 0;
}