#include <fstream>
#define ub(n) (n & (-n))

using namespace std;

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

int N, M, c, x, j, a, b, SS;
int AIB[100003];

int add(int poz, int val) {
    for(int i = poz; i <= N; i += ub(i)) AIB[i] += val;
    return 0;
}
int sum(int poz) {
    int sum = 0;
    for(int i = poz; i >= 1; i -= ub(i)) sum += AIB[i];
    return sum;
}
int cautbin(int n) {
    int st = 1, dr = N, mij = 0;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if(n <= sum(mij))   dr = mij - 1;
        else                st = mij + 1;
    }
    return st;
}
int main()
{
    f >> N >> M;
    for(int i = 1; i <= N; i++)
        f >> x, add(i, x);
    for(int i = 1; i <= M; i++) {
        f >> c;
        if(c == 0) f >> j >> x, add(j, x);
        else if(c == 2) {
            f >> x, SS = cautbin(x);
            if(AIB[SS] != x) g << -1 << "\n";
            else        g << SS << "\n";
        }
        else if (c == 1) f >> a >> b, g << sum(b) - sum(a-1) << "\n";
    }
    return 0;
}