#include <bits/stdc++.h>

using namespace std;
int aib[100005], t, a, b, x, i, n, m, l, r, mij, sol;
void update(int val, int poz)
{
    for(; poz <= n; poz += (poz & (-poz)))
        aib[poz] += val;
}
int query(int poz)
{
    int ret = 0;
    for(; poz; poz -= (poz & (-poz)))
        ret += aib[poz];
    return ret;
}
int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        update(x, i);
    }
    for(; m; m--)
    {
        scanf("%d%d", &t, &a);
        if(!t)
        {
            scanf("%d", &b);
            update(b, a);
            continue;
        }
        if(t == 1)
        {
            scanf("%d", &b);
            printf("%d\n", query(b) - query(a - 1));
            continue;
        }
        l = 1;
        r = n;
        sol = n + 1;
        while(l <= r)
        {
            mij = (l + r) / 2;
            x = query(mij);
            if(x < a)
                l = mij + 1;
            else
            {
                if(x == a)
                    sol = mij;
                r = mij - 1;
            }
        }
        sol == n + 1 ? printf("-1\n") : printf("%d\n", sol);
    }
    return 0;
}