#define pas(x) (x & (-x))
#include <cstdio>

using namespace std;

int aib[100010], x;
int N, M, nr;
int Type, a, b, k;

void Add(int nr, int poz)
{
    for(int i=poz; i<=N; i+=pas(i))
        aib[i]+=nr;
}

int sum(int poz)
{
    int rez = 0;
    for(int i=poz; i>0; i-=pas(i))
        rez += aib[i];
    return rez;
}

int suma_egala(int k)
{
    int rez = 0, i=1;
    bool ok = true;
    while(true)
    {
        if(rez + aib[i+pas(i)] > k)
        {
            int auxp = pas(i)>>1;
            while(rez + aib[i + auxp] > k)
                auxp >>= 1;
            i+=auxp;
            ok = false;
            if(rez + aib[i] == k)
                return i;
        }
        if(rez + aib[i+pas(i)] == k)
            return i+pas(i);
        if(i < 1)
            return -1;
        if(ok == true)
            i+=pas(i);
        ok = true;
    }
}


int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for(int i=1; i <= N; i++)
    {
        scanf("%d", &nr);
        Add(nr, i);
    }
    for(int querry = 1; querry <= M; ++ querry)
    {
        scanf("%d", &Type);
        if(Type < 2)
        {
            scanf("%d %d", &a, &b);
            if(Type == 0)
                Add(b, a);
            else printf("%d\n", sum(b) - sum(a-1));
        }
        else{
            scanf("%d", &k);
            printf("%d\n", suma_egala(k));
        }
    }
    return 0;
}