#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;
    bool ok = 0;
    int lg = 1;
    for(lg; lg<=N; lg<<=1);
    int i;
    for(i=1; lg != 0; lg >>= 1)
        if(i + lg <= N && sum(i+lg) <= k)
            i += lg;
    if(sum(i) != k)
        return -1;
    return i;


}


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;
}