#include <fstream>
#include<vector>
#define zeroes(x) (x^(x-1))&x
using namespace std;
int n,m,x,k,y;
vector<int> aib;
ifstream f("aib.in");
ofstream g("aib.out");
void Update(int ind,int nr)
{
    for(int i=ind;i<=n;i+=zeroes(i))
        aib[i]+=nr;
}
int Suma(int ind)
{
    int sum=0;
    for(int i=ind;i;i-=zeroes(i))
        sum+=aib[i];
    return sum;
}
int Cauta(int k)
{
    int step;
    for(step=1;step<n;step<<=1);
    for(int i=0;step;step>>=1)
        if(k>=aib[i+step])
            {
                i+=step;k-=aib[i];
                if(!k) return i;
            }
    return -1;
}
int main()
{
    f>>n>>m;aib.resize(n+1);
    for(int i=1;i<=n;i++)
        {
            f>>x;
            Update(i,x);
        }
    for(int i=1;i<=m;i++)
        {
            f>>k;
            if(!k) {f>>x>>y;Update(x,y);}
            else if(k==1) {f>>x>>y;g<<Suma(y)-Suma(x-1)<<'\n';}
            else {f>>x;g<<Cauta(x)<<'\n';}
        }
    return 0;
}