#include <iostream>
#include <fstream>

using namespace std;

int n,m,aib[100005];

void adaug(int nr,int poz)
{
    for(int i=poz;i<=n;i+=(i&(-i)))
        aib[i]+=nr;
}

int suma(int poz)
{
    long long sum=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        sum+=aib[i];
    return sum;
}

int pozitie(int x)
{
    int p;
    for(p=1;p<=n;p<<=1);
    for(int i=0;p;p>>=1)
    {
        if(i+p<=n&&x>=aib[i+p])
        {
            i+=p;
            x-=aib[i];
            if(!x)
                return i;
        }
    }
    return -1;
}

void citireafisare()
{
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin>>n>>m;
    int a,b,t;
    for(int i=1;i<=n;i++)
    {
        fin>>a;
        adaug(a,i);
    }
    for(int i=0;i<m;i++)
    {
        fin>>t>>a;
        if(t==0)
        {
            fin>>b;
            adaug(b,a);
        }
        else if(t==1)
        {
            fin>>b;
            fout<<suma(b)-suma(a-1)<<"\n";
        }
        else
            fout<<pozitie(a)<<"\n";
    }
}

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