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

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

const int NMAX = 100000;

int N, AiB[NMAX + 1];

void add(int poz, int val = 1)
{
    while(poz <= N)
    {
        AiB[poz] += val;
        poz += poz & (-poz);
    }
}

int sum(int poz)
{
    int s = 0;
    while(poz > 0)
    {
        s += AiB[poz];
        poz -= poz & (-poz);
    }
    return s;
}

int bsearch(int val)///cautare binara "naiva"
{
    int p = 1, u = N, poz = -1;
    while(p <= u)
    {
        int m = (p + u) >> 1,
            s = sum(m);
        if(s < val)
            p = m + 1;
        else
        {
            if(s == val)
                poz = m;
            u = m - 1;
        }
    }
    return poz;
}

int main()
{
    int M, op, x, y;
    f >> N >> M;
    for(int i = 1; i <= N; i++)
    {
        f >> x;
        add(i, x);
    }
    //
    while(M--)
    {
        f>>op;
        switch(op)
        {
        case 0:
            f >> x >> y;
            add(x, y);
            break;
        case 1:
            f >> x >> y;
            g << sum(y) - sum(x - 1) << '\n';
            break;
        case 2:
            f >> x;
            g << bsearch(x) << '\n';
        }
    }
    return 0;
}