#include <iostream>
#include <fstream>
using namespace std;
#include <vector>
#include <math.h>
#include <stdlib.h>

namespace e_015_aib_4_
{
	int pa(int i) { return (i + 1) / 2; }
	int ch1(int i) { return 2 * i - 1; }

	void build_sums(int N, int* v, int& max_level, int**& sums)
	{
		//calculate the number of levels
		int k = 0;
		while (1 << k < N) k++;
		max_level = k;
		//sums.resize(k + 1); 
		sums = new int*[k + 1];
		
		//first level
		//sums[0].resize(N + 1);
		sums[0] = new int[N + 1];
		for (int i = 1; i <= N; i++) sums[0][i] = v[i];
		
		//the other levels
		int l = 1;
		//int sz = sums[0].size() - 1;
		int sz = N;
		while ( sz > 1 ) {
			int szl = (sz + 1) / 2;
			//sums[l].resize(szl + 1);
			sums[l] = new int[szl + 1];
			for (int i = 1; i <= szl; i++) {
				int c1 = ch1(i);
				int c2 = c1 + 1;

				if (c2 <= sz) sums[l][i] = sums[l - 1][c1] + sums[l - 1][c2];
				else sums[l][i] = sums[l - 1][c1];
			}

			sz = szl;
			l++;
		}
	}

	void add_to(int pos, int val, int max_level, int** sums)
	{
		//pos is in the first level; update all the levels
		for (int l = 0; l <= max_level; l++) {
			sums[l][pos] += val;
			pos = pa(pos);
		}
	}
	
	int sum_up_to(int a, int** sums)
	{
		int sum = 0;
		int elms = 0; //the number of elements skipped so far
		while (a != 0) {
			int k = (int)log2(a); //the level
			int tk = 1 << k;
			int j = elms/tk + 1;//the index in level

			sum += sums[k][j];
			elms += tk;
			a = a - tk;
		}

		return sum;
	}

	int sum(int a, int b, int** sums)
	{
		return sum_up_to(b, sums) - sum_up_to(a - 1, sums);;
	}

	int id_sum(int s, int level, int node, int** sums)
	{
		int sln = sums[level][node];
		if (sln < s) return -1; //the current node has the sum < s, no index here
		else if (sln == s) return node * (1 << level);
		else {// if (sln > s) {
			if (level == 0) return -1; //no childs to search for sums

			int lm1 = level - 1;
			//look in childs
			int c1 = ch1(node), c2 = c1 + 1;
			int rem = s - sums[lm1][c1]; //the remainder after the first child
			if (rem <= 0) return id_sum(s, lm1, c1, sums);
			else return id_sum(rem, lm1, c2, sums);
		}
	}

}

//int e_015_aib_4()
int main()
{
	using namespace e_015_aib_4_;

	int N, M;
	int* v;

	ifstream ifs("aib.in");
	ofstream ofs("aib.out");
	
	ifs >> N >> M;
	v = new int[N + 1];
	for (int i = 1; i <= N; i++) ifs >> v[i];
	
	int** sums;
	int max_level;
	build_sums(N, v, max_level, sums);

	for (int i = 1; i <= M; i++) {
		int op, a, b;
		ifs >> op;
		if (op == 0) {
			ifs >> a >> b;
			add_to(a, b, max_level, sums);
		}
		else if (op == 1) {
			ifs >> a >> b;
			ofs << sum(a, b, sums) << "\n";
		}
		else {
			ifs >> a;
			ofs << id_sum(a, max_level, 1, sums) << "\n";
		}
	}

	ofs.close();
	ifs.close();

	delete[] v;
	for (int i = 0; i <= max_level; i++) delete[] sums[i];
	delete[] sums;

	system("pause");

	return 0;
}