#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 find2(int val) {
	int x, pas, sum;
	for(x = 1; x <= n; x <<= 1)
		;
	x /= 2;
	pas = x/2;
	sum = 0;
	while(true) {
		if(sum + aib[x] <= val) {
			sum += aib[x];
			if(sum == val) return x;
			while(x + pas > n) pas /= 2;
			x += pas;
		} else {
			x -= pas;
		}
		if(pas == 0) break;
		pas /= 2;
	}
	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 << find2(a) << "\n";
		}
	}
	return 0;
}