#include <bits/stdc++.h>

using namespace std;

int n,m,arb[100005];

int nr_zerfin(int x)
{
    return ((x xor(x-1))&x);
}
void update(int x,int i)
{
    while(i<=n)
    {
        arb[i]+=x;
        i+=nr_zerfin(i);
    }
}
int aflu_suma(int poz) ///suma termenilor pana in poz
{
    int s=0;
    while (poz>=1)
    {
        s+=arb[poz];
        poz-=nr_zerfin(poz);;
    }
    return s;
}
int caut_binar(int a)
{
    int st=1,dr=n;
    int mij=(st+dr)/2;
    while (st<=dr)
    {
        int sum=aflu_suma(mij);
        if (sum==a)
            return mij;
        if (a>sum)
            st=mij+1;
        else
            dr=mij-1;
        mij=(st+dr)/2;
    }
    return -1;
}
void citire_solve()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        update(x,i);
    }
    int op,a,b;
    for (int i=1;i<=m;++i)
    {
        scanf("%d",&op);
        if (op<2)
        {
            scanf("%d%d",&a,&b);
            if (op==0)
            {
                update(b,a);
            }
            else
            {
                printf("%d\n",aflu_suma(b)-aflu_suma(a-1));
            }
        }
        else
        {
            scanf("%d",&a);
            printf("%d\n",caut_binar(a));
        }
    }
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    citire_solve();

    return 0;
}