#include <cstdio>
#define zeros(x) ((x ^ (x-1)) & x)
using namespace std;

int n, m, c, x, y, i, j, k, s1, s2, aib[100005];

void add(int x, int y) {
    for(int i = x; i <= n; i += zeros(i))
        aib[i] += y;
}

int sum(int x) {
    int s = 0;
    for(int i = x; i > 0; i -= zeros(i))
        s += aib[i];
    return s;
}

int cautbin(int s) {
    int m, temp, st = 1, dr = n;
    while(st <= dr) {
        m = (st + dr) / 2;
        temp = sum(m);
        if(temp == s)
            return m;
        else if(temp > s)
            dr = m-1;
        else
            st = m + 1;
    }
    return -1;
}

int main() {

    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; ++i) {
        scanf("%d", &x);
        add(i, x);
    }

    for(i = 1; i <= m; ++i) {
        scanf("%d%d", &c, &x);
        if(c == 0) {
            scanf("%d", &y);
            add(x, y);
        }

        else if(c == 1) {
            scanf("%d", &y);
            printf("%d\n", sum(y) - sum(x-1));
        }

        else
            printf("%d\n", cautbin(x));
    }
}