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

namespace e_015_aib_6_
{	
	int end_zeros(int i)
	{
		int k = 0;
		while (i % 2 == 0) { k++; i >>= 1; }

		return k;
	}

	int parent(int i)
	{
		int k = end_zeros(i);
		return i + (1 << k);
	}

	void add_to(int i, int val, int N, int* aib)
	{
		while (i <= N) {
			aib[i] += val;
			i = parent(i);
		}
	}

	int sum_up_to(int i, int* aib)
	{
		if (i <= 0) return 0;

		int sum = 0;
		//find the binary decomposition of i
		//inverts the digits
		int d = 0; //number of digits
		int inv_i = 0;
		while (i) {
			int c = i % 2;
			inv_i = (inv_i << 1) + c;
			i >>= 1;
			d++;
		}

		int pow = 1 << (d-1);
		int ind = 0;
		for (int i = 1; i <= d; i++) {
			int c = inv_i % 2;
			if (c) {
				ind += c * pow;
				sum += c * aib[ind];
			}
			inv_i >>= 1;
			pow >>= 1;
		}

		return sum;
	}

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

	int id_sum(int s, int N, int* aib)
	{
		if (N == 0 || s < aib[1]) return -1;

		int ind = 1;
		while (ind <= N && aib[ind] <= s) ind <<= 1;
		ind >>= 1;

		if (s == aib[ind]) return ind;
		//otherwise
		int id_rem = id_sum(s - aib[ind], N - ind, aib + ind);
		if (id_rem == -1) return -1;
		return ind + id_rem;
	}
}

//int e_015_aib_6()
int main()
{
	using namespace e_015_aib_6_;

	int N, M;

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

	ifs >> N >> M;
	int* aib = new int[N + 1];
	for (int i = 1; i <= N; i++) aib[i] = 0;
	//read the leaf nodes
	for (int i = 1; i <= N; i++) {
		int x; ifs >> x;
		add_to(i, x, N, aib);
	}

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

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

	delete[] aib;

	return 0;
}