#include <fstream>
#include <vector>

std::vector <int> aib;

void update(int val, int pos) {
	while (pos < aib.size()) {
		aib[pos] += val;
		pos += (pos & -pos);
	}
}

int query(int pos) {
	int ans = 0;
	while (pos) {
		ans += aib[pos];
		pos &= pos - 1;
	}
	return ans;
}

int main() {
	std::ifstream fin("aib.in");
	std::ofstream fout("aib.out");
	int nrn, nrq, nri, cer, nr1, nr2;
	int val1, val2, mid;
	fin >> nrn >> nrq;
	aib.resize(nrn + 1);
	for (int index = 1; index <= nrn; index++) {
		fin >> nri;
		update(nri, index);
	}
	for (int index = 0; index < nrq; index++) {
		fin >> cer >> nr1;
		if (cer == 0) {
			fin >> nr2;
			update(nr2, nr1);
		}
		if (cer == 1) {
			fin >> nr2;
			fout << query(nr2) - query(nr1 - 1) << '\n';
		}
		if (cer == 2) {
			val1 = 0;
			val2 = aib.size();
			while (val2 - val1 > 1) {
				mid = (val1 + val2) / 2;
				if (query(mid) < nr1) {
					val1 = mid;
				}
				else {
					val2 = mid;
				}
			}
			if (query(val2) == nr1) {
				fout << val2 << '\n';
			}
		}
	}
}