#include <fstream>
#define NMAX 100010

using namespace std;

FILE *fin, *fout;

int n, m, aib[NMAX];

void update(int x, int q);
int calcul(int x); //suma pe [1,2, ... x]
int cautare_binara(int x);
int zeros(int x);

int main()
{
    int i, tip, a, b, x;
    fin = fopen("aib.in", "r");
    fout = fopen("aib.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 1; i <= n; i++)
    {
        fscanf(fin, "%d", &x);
        update(i, x);
    }
    for (i = 1; i <= m; i++)
    {
        fscanf(fin, "%d", &tip);
        if (!tip)
        {
            fscanf(fin, "%d%d", &a, &b);
            update(a, b);
        }
        else if (tip == 1)
        {
            fscanf(fin, "%d%d", &a, &b);
            fprintf(fout, "%d\n", calcul(b) - calcul(a - 1));
        }
        else
        {
            fscanf(fin, "%d", &a);
            fprintf(fout, "%d\n", cautare_binara(a));
        }
    }
    fclose(fout);
    return 0;
}

void update(int x, int q)
{
    int i;
    for (i = x; i <= n; i += zeros(i))
        aib[i] += q;
}
int calcul(int x)
{
    int i, rez = 0;
    for (i = x; i > 0; i -= zeros(i))
        rez += aib[i];
    return rez;
}
int cautare_binara(int x)
{
    int st = 1, dr = n, mij, rez;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        rez = calcul(mij);
        if (rez < x)
            st = mij + 1;
        else if (rez > x)
            dr = mij - 1;
        else
            return mij;
    }
    return -1;
}
int zeros(int x)
{
    return (x & (-x));
}