#include <fstream>

using namespace std;
int n,m,k,i,a,b,c,j,v[18][100005];
void adauga(int x, int poz)
{
    j=0;
    while(j<=k)
    {
        v[j][poz]+=x;
        poz=(poz+1)/2;
        j++;
    }
}
int suma(int poz)
{
    j=0;
    int s=v[0][poz];
    while(poz>1)
    {
        if(poz%2==0) s+=v[j][poz-1];
        j++;
        poz=(poz+1)/2;
    }
    return s;
}
int poz(int s)
{
    j=k;
    int x=1;
    while(j>0)
    {
        j--;
        x=2*x-1;
        if(v[j][x]<s)
        {
            s-=v[j][x];
            x++;
        }
    }
    if(s==v[0][x]) return x;
    return -1;
}
int main()
{
    ifstream f("aib.in");
    ofstream g("aib.out");
    f>>n;
    m=n;
    while(m>1)
    {
        k++;
        m=(m+1)/2;
    }
    f>>m;
    for(i=1; i<=n; i++)
    {
        f>>a;
        adauga(a,i);
    }
    for(i=1; i<=m; i++)
    {
        f>>c;
        if(c==0)
        {
            f>>b>>a;
            adauga(a,b);
        }
        else if(c==1)
        {
            f>>a>>b;
            g<<suma(b)-suma(a-1)<<'\n';
        }
        else
        {
            f>>a;
            g<<poz(a)<<'\n';
        }
    }
    f.close(); g.close();
    return 0;
}