#include <iostream>
#include <vector>
#include <climits>
#include<unordered_map>
#include <algorithm>
#include <set>
#include<string>
#include<map>
#include<queue>
#include<cmath>
#include<fstream>
#include<list>
#include<iomanip>
using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");
#define INF 1000000

int A[100005];
int n;
void update(int poz, int n, int val) {
	for (int i = poz; i <= n; i+=(i&-i)) {
		A[i]+=val;
	}
}

int query(int poz, int n) {
	int sum = 0;
	for (int i = poz; i; i -= (i & -i)) {
		sum += A[i];
	}
	return sum;
}

int binar(int n, int a) {
	int st = 1, dr = n;
	while (st <= dr) {
		int mijl = (dr + st) / 2;
		int val = query(mijl, n);
		if (val == a)return mijl;
		else if (val < a)st = mijl + 1;
		else dr = mijl;
	}
	return -1;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	in >> n>>m;
	for (int i = 1; i <= n; i++) {
		int x;
		in >> x;
		update(i, n, x);
	}
	while (m--) {
		int op;
		in >> op;
		if (op == 0) {
			int a, b;
			in >> a >> b;
			update(a, n, b);
		}
		else if (op == 1) {
			int a, b;
			in >> a >> b;
			out << query(b, n) - query(a - 1, n) << "\n";
		}
		else {
			int a;
			in >> a;
			out << binar(n, a)<<"\n";
		}
	}
}