#include <fstream>
#include <vector>
using namespace std;

#define in "aib.in"
#define out "aib.out"
#define N 100005

vector <int> aib (N, 0);
int n, m;

void add (int i, int v) {
	while (i <= n) {
		aib[i] += v;
		i += (i^(i-1)) & i;
	}
}

int query (int i) {
	int s = 0;
	while (i > 0) {
		s += aib[i];
		i -= (i^(i-1)) & i;
	}
	return s;
}

int BS (int x) {
	int lo = 1, hi = n+1;
	while (lo < hi) {
		int mid = (lo + hi) >> 1;
		int val = query (mid);
		if (val == x)
			return mid;
		else
			if (val < x)
				lo = mid + 1;
		else
			hi = mid;
	}
	return -1;
}

int main () {
	ifstream fin (in);
	fin >> n >> m;
	for (int i = 1; i <= n; ++i)  {
		int x;
		fin >> x;
		add (i, x);
	}
	ofstream fout (out);
	for (int i = 0; i < m; ++i) {
		int type;
		fin >> type;
		if (!type) {
			int a, b;
			fin >> a >> b;
			add (a, b);
		}
		else
			if (type == 1) {
				int a, b;
				fin >> a >> b;
				fout << query (b) - query (a-1) << "\n";
			}
		else {
			int x;
			fin >> x;
			fout << BS (x) << "\n";
		}
	}
	fcloseall();
	return 0;
}