#include<fstream>
using namespace std;

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

int n, m, aib[100001];

inline int lsb(int val) {
	int ans = 0;
	while((val & 1) == 0) {
		ans++;
		val >>= 1;
	}
	return ans;
}

inline int exp(int val) {
	int ans = 1, i;
	for(i = 0; i < val; i++) ans *= 2;
	return ans;
}

void update(int poz, int val) {
	while(poz <= n) {
		aib[poz] += val;
		poz += exp(lsb(poz));
	}
}

int query(int poz) {
	int ans = 0;
	while(poz > 0) {
		ans += aib[poz];
		poz -= exp(lsb(poz));
	}
	return ans;
}

int query(int a, int b) {
	return query(b) - query(a-1);
}

int find(int val) {
	int left = 1, right = n, m, ans = -1;
	while(left <= right) {
		m = (left + right) / 2;
		if(query(m) > val) {
			right = m-1;
		} else {
			left = m+1;
			ans = m;
		}
	}
	if(query(ans) == val) return ans;
	return -1;
}

int main() {
	int tip, a, b, i;
	fin >> n >> m;
	for(i = 1; i <= n; i++) {
		fin >> a;
		update(i, a);
	}
	for(i = 0; i < m; i++) {
		fin >> tip;
		if(tip == 0) {
			fin >> a >> b;
			update(a, b);
		}
		if(tip == 1) {
			fin >> a >> b;
			fout << query(a, b) << "\n";
		}
		if(tip == 2) {
			fin >> a;
			fout << find(a) << "\n";
		}
	}
	return 0;
}