#include <fstream>
#include <algorithm>
#define zeros(nr) ((nr^(nr-1))&nr)
std::ifstream fin("aib.in");
std::ofstream fout("aib.out");

class AIB
{
private:
	int *aib;
	int N;

public:
	AIB();
	~AIB();
	void CreateAIB(int);
	void add(int, int);
	int query(int);
	int queryRange(int, int);
	int Bsearch(int);
};


int main()
{
	AIB copac;
	int n, m;
	fin >> n >> m;
	copac.CreateAIB(n);
	for (int i = 0; i < n; ++i) {
		int nr;
		fin >> nr;
		copac.add(i + 1, nr);
	}

	for (int i = 0; i < m; ++i)
	{
		int q, a, b;
		fin >> q;
		if (q == 0) {
			fin >> a >> b;
			copac.add(a, b);
		} else if (q == 1) {
			fin >> a >> b;
			fout << copac.queryRange(a, b) << "\n";
		} else if (q == 2) {
			fin >> a;
			fout << copac.Bsearch(a) << "\n";
		}
	}
	return 0;
}

AIB::AIB() {
	aib = NULL;
	N = 0;
}
AIB::~AIB() {
	delete[] aib;
}

void AIB::CreateAIB(int n) {
	this->aib = new int[n + 10]();
	this->N = n;
}

void AIB::add(int pos, int nr) {
	for (int i = pos; i <= N; i += zeros(i)) {
		this->aib[i] += nr;
	}
}

int AIB::query(int pos) {
	int ret = 0;
	for (int i = pos; i > 0; i -= zeros(i)) {
		ret += this->aib[i];
	}
	return ret;
}

int AIB::queryRange(int l, int r) {
	return this->query(r) - this->query(l - 1);
}

int AIB::Bsearch(int nr) {
	int l = 1;
	int r = N;
	while (l <= r) {
		int mid = (l + r) / 2;
		int val = query(mid);
		if (val == nr) {
			return mid;
		}
		if (nr < val) {
			r = mid - 1;
			continue;
		} else {
			l = mid + 1;
			continue;
		}
	}
	return -1;
}