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

namespace e_015_aib_5_
{
	int pa(int i) { return i / 2; }
	int ch1(int i) { return 2 * i; }

	int build_sums(int node, int twos, int N, int* sums)
	{		
		if (node > twos + N) return 0; //outside the range
		if (node > twos) return sums[node]; //if a leaf
		//otherwise sum up the childs
		int c1 = ch1(node);
		int c2 = c1 + 1;
		int ls = build_sums(c1, twos, N, sums);
		int rs = build_sums(c2, twos, N, sums);
		sums[node] = ls + rs;

		return sums[node];
	}

	void add_in_tree(int node, int val, int* sums)
	{
		sums[node] += val;
		if (node == 1) return;
		add_in_tree(pa(node), val, sums);
	}

	void add_to(int pos, int val, int twos, int* sums)
	{
		int node = twos + pos;
		add_in_tree(node, val, sums);
	}	

	int sum_up_to(int a, int node, int level, int* sums)
	{
		//if (level == 0) return sums[1]; //a should be 1
		//otherwise
		if (a <= 0) return 0;

		int elms = 1 << level;
		if (a == elms) return sums[node];
		else if (a < elms) { //a > elms not possible
			int c1 = ch1(node);
			int c2 = c1 + 1;
			int ls = sum_up_to(a, c1, level - 1, sums);
			int elms1 = 1 << (level - 1); //the number of elements of the first child
			int rs = sum_up_to(a - elms1, c2, level - 1, sums);

			return ls + rs;
		}	

		// a > elms not possible by convention
		return sums[node];
	}

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

	int id_sum(int s, int node, int level, int twos, int N, int* sums)
	{		
		if (node > twos + N) return -1; //outside the range
		if (level == 0) {
			if (sums[node] == s) return 1;
			else return -1;
		}

		int sum_all = sums[node];
		if (s > sum_all) return -1; //cannot achieve that much
		if (s == sum_all) return 1 << level; //the index
		
		//if s < sum_all, look in childs
		int c1 = ch1(node), c2 = c1 + 1; //the childs
		int id;
		int new_s = s - sums[c1];
		if (new_s <= 0) id = id_sum(s, c1, level - 1, twos, N, sums);
		else {
			id = id_sum(new_s, c2, level - 1, twos, N, sums);
			if (id > 0) id += 1 << (level - 1);
		}

		return id;
	}

}

//int e_015_aib_5()
int main()
{
	using namespace e_015_aib_5_;

	int N, M;

	ifstream ifs("aib.in");
	ofstream ofs("aib.out");

	ifs >> N >> M;
	
	int max_level = (int)log2(N-1) + 1;
	int twos = (1 << max_level) - 1;
	int* sums = new int[twos + N + 1];
	int* sums_ = sums + twos;
	//read the leaf nodes
	for (int i = 1; i <= N; i++) ifs >> sums_[i];

	build_sums(1, twos, N, sums);

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

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

	delete[] sums;

	return 0;
}