#include <iostream>
#define MAX_N 100005

int fenwick[MAX_N * 2];
int fenwickSize;

void add(int pos, int val)
{
    while (pos <= fenwickSize) {
        fenwick[pos] += val;
        pos = pos + (pos & (-pos));
    }
}

int getUntilEq(int pos)
{
    int sum = 0;
    while (pos >= 1) {
        sum += fenwick[pos];
        pos = pos - (pos & (-pos));
    }
    return sum;
}

int binary_search(int low, int high, int val)
{
    if (low == high) {
        return low;
    }
    if (low == high - 1) {
        if (getUntilEq(low) >= val)
            return low;
        return high;
    }
    int mid = (low + high) / 2;
    if (getUntilEq(mid) >= val)
        return binary_search(low, mid, val);
    return binary_search(mid, high, val);
}
int n, m;

int task2(int a)
{
    int possible = binary_search(1, n, a);
    if (getUntilEq(possible) != a)
        return -1;
    return possible;
}

int main()
{
    FILE *fin = fopen("aib.in", "r");
    FILE *fout = fopen("aib.out", "w");
    fscanf(fin, "%d %d", &n, &m);
    fenwickSize = 1;
    while (fenwickSize < n)
        fenwickSize = fenwickSize * 2;

    for (int i = 0; i < n; i++) {
        int c;
        fscanf(fin, "%d", &c);
        add(i + 1, c);
    }
    for (int i = 0; i < m; i++) {
        int t, a, b;
        fscanf(fin, "%d %d", &t, &a);
        if (t == 0 || t == 1)
            fscanf(fin, "%d", &b);
        if (t == 0) {
            add(a, b);
        } else if (t == 1) {
            fprintf(fout, "%d\n", getUntilEq(b) - getUntilEq(a - 1));
        } else {
            fprintf(fout, "%d\n", task2(a));
        }
    }
}