#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define VMAX 200005
using namespace std;
ifstream fin ("aib.in");
ofstream fout ("aib.out");

int val[VMAX];


int querry(int nr)
{
    int suma=0;
    while(nr)
    {
        suma+=val[nr];
        nr-=nr&(-nr);
    }
    return suma;
}

void update(int nr, int adg)
{
    while(nr<VMAX)
    {
        val[nr]+=adg;
        nr+=nr&(-nr);
    }
    //val[VMAX-1]+=adg;
}

int total(int k)
{
    int nr = 1,i;
    for(i=1;(1ll<<i)<VMAX;i++);
    i--;
    nr=0;

    for(;i>=0;i--)
    {
        if(val[nr+(1ll<<i)]<k)
            nr+=(1ll<<i), k-=val[nr];
    }
    return nr;



}


int main()
{
    ios_base::sync_with_stdio(0);
    long long int n,m,i,j,k,t,q,nr,minim,maxim,suma,x,y,z;
    fin>>n>>m;

    for(i=1;i<=n;i++)
    {
        fin>>j;
        update(i,j);
    }


    for(i=0;i<m;i++)
    {
        fin>>k;
        if(k==0)
        {
            fin>>j>>k;
            update(j,k);
        }
        else if(k==1)
        {
            fin>>j>>k;
            j--;
            fout<<querry(k)-querry(j)<<'\n';
        }
        else
        {
            fin>>j;
            k=total(j);
            k++;
            if(querry(k)!=j)
                fout<<"-1\n";
            else
                fout<<k<<'\n';
        }
    }





    return 0;
}