#include <cstdio>

#define Max_Size 100008
#define zeros(x) x & (-x)

using namespace std;

const char iname[] = "aib.in";
const char oname[] = "aib.out";

int N, M, AIB[Max_Size];

inline void Set(int poz, int val)
{
    for(int i = poz; i <= N; i += zeros(i))
        AIB[i] += val;
}

inline int Get(int a)
{
    int sum = 0;

    for(int i = a; i > 0; i -= zeros(i))   sum += AIB[i];

    return sum;
}

int main()
{
    FILE *in = fopen(iname, "r");
    FILE *out = fopen(oname, "w");

    fscanf(in, "%d%d", &N, &M);

    for(int x, i = 1; i <= N; ++i)  {
        fscanf(in, "%d", &x);
        Set(i, x);
    }

    for(int t, a, b, i = 1; i <= M; ++i)    {
        fscanf(in, "%d", &t);

        if(!t)  {
            fscanf(in, "%d%d", &a, &b);
            Set(a, b);

            continue;
        }
        if(t == 1)  {
            fscanf(in, "%d%d", &a, &b);
            fprintf(out, "%d\n", Get(b) - Get(a - 1));

            continue;
        }
        fscanf(in, "%d", &a);

        int st = 1 , dr = N, K = -1;

        while(st <= dr) {
            int mij = (st + dr) >> 1;

            int sum = Get(mij);

            if(sum >= a)   {
                if(sum == a)    K = mij;
                dr = mij - 1;
            }
            else
                st = mij + 1;
        }

        fprintf(out, "%d\n", K);
    }

    return 0;
}