#include <fstream>
#include <cmath>
using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int n,m,v[100005],i,a,b,c,k;

void adauga(int val, int poz)
{
    if(poz<=n)
    {
        v[poz]+=val;
        k=0,b=poz;
        while(b && b%2==0)
            k++,b/=2;
        adauga(val,poz+(pow(2,k)));
    }
}

long long suma(int poz)
{
    int aux;
    if(poz>0)
    {
        k=0,aux=poz;
        while(aux && aux%2==0)
            k++,aux/=2;
        return v[poz] + suma(poz-pow(2,k));
    }
    else return 0;
}

int cautBinar(int st,int dr,long long val)
{
    int mijloc = (st+dr)/2;
    long long ss=suma(mijloc);
    if(ss==val) return mijloc;
    if(ss>val) cautBinar(st,mijloc,val);
    else cautBinar(mijloc+1,dr,val);
}

int main()
{
    f>>n>>m;

    for(i=1;i<=n;i++)
        v[i]=0;

    for(i=1;i<=n;i++)
        f>>a,adauga(a,i);

    while(m)
    {
        f>>a>>b;
        if(!a)
            f>>c,adauga(c,b);
        else
            if(a==1)
                f>>c,g<<suma(c)-suma(b-1)<<'\n';
            else
            {
                int pp = cautBinar(1,n,b);
                if(suma(pp)==b)
                    g<<pp<<'\n';
                else
                    g<<-1<<'\n';
            }
        m--;
    }
    return 0;
}