#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

const int nmax = 100001;
int n,m;
long long aib[2*nmax];

void update(int index, int value) {
    for (int i = index; i <= n; i += i&-i) {
        aib[i] += value;
    }
}

int getSum(int index) {
    int ret = 0;
    for (; index > 0; index -= index&-index) {
        ret += aib[index];
    }
    return ret;
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int rd;
        fin >> rd;
        update(i, rd);
    }

    while (m--) {
        int t;
        fin >> t;
        switch (t) {
            case 0: {
                int a,b; fin >> a >> b;
                update(a,b);
                break;
            }
            case 1: {
                int a,b; fin >> a >> b;
                fout << getSum(b) - getSum(a-1) << '\n';
                break;
            }

            case 2: {
                int a; fin >> a;
                int left = 1;
                int right = n;
                bool found = false;
                while (left <= right) {
                    const int mid = left + (right - left) / 2;
                    const int sum = getSum(mid);
                    if (sum > a) {
                        right = mid;
                    } else if (sum < a) {
                        left = mid + 1;
                    } else {
                        found = true;
                        fout << mid << '\n';
                        break;
                    }
                }
                if (!found) {
                    fout << -1 << '\n';
                }
                break;
            }
        }
    }

    return 0;
}