// aib.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

//#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cstdio>

using std::cout;
using std::vector;
using std::ifstream;
using std::ofstream;
using std::for_each;

template <typename T>
class FenwickTree {
public:

	explicit FenwickTree(vector<T>& elements)
		: elements{ elements } {

		__build();
	}

	T prefixSum(int position) {

		T sum = 0;
		for (int start = position; start > 0; start = getParent(start)) {
			sum += tree[start];
		}

		return sum;
	}

	T intervalSum(int first, int second) {
		return prefixSum(second) - prefixSum(first) + elements[first - 1];
	}

	void update(int position, const T& value) {

		for (int next = position; next < tree.size(); next = getNext(next)) {
			tree[next] += value;
		}

		elements[position - 1] += value;
	}

private:

	void __build() {
		tree.resize(elements.size() + 1);

		for (int i = 1; i < tree.size(); ++i) {
			__propagateToNext(i);
		}
	}

	void __propagateToNext(int i) {
		const T& val = elements[i - 1];

		for (int next = i; next < tree.size(); next = getNext(next)) {
			tree[next] += val;
		}
	}

	int getNext(int x) {
		return	x + ((~x + 1) & x);
	}

	int getParent(int x) {
		return x - ((~x + 1) & x);
	}

	vector<T>& elements;
	vector<T> tree;
};

class SearchFenwickTree : public FenwickTree<int> {

public:
	explicit SearchFenwickTree(vector<int>& elements) 
		: FenwickTree<int>{ elements }, elements{ elements } {
	}

	int search(int x) {

		return __search(
			1,
			elements.size(),
			x
		);
	}

private:
	vector<int>& elements;

	int __search(int a, int b, int el) {

		if (a > b) {
			return -1;
		}

		int mid = (a + b) >> 1;

		int value = prefixSum(mid);

		if (value == el) {
			return mid;
		}

		return value > el ? __search(a, mid - 1, el) : __search(mid + 1, b, el);
	}
};


void answer(SearchFenwickTree& t, int M, FILE* fin, FILE* fout) {

	while (M-- > 0) {

		int type; fscanf(fin, "%d", &type);

		switch (type) {
			case 0: {
				int a, b; fscanf(fin, "%d %d", &a, &b);
				t.update(a, b);
				break;
			}
			case 1: {
				int a, b; fscanf(fin, "%d %d", &a, &b);
				fprintf(fout, "%d\n", t.intervalSum(a, b));
				break;
			}
			default: {
				int eq; fscanf(fin, "%d", &eq);
				fprintf(fout, "%d\n", t.search(eq));
			}
		}
	}

}

void solve() {

	FILE* fin = fopen("aib.in", "r");
	FILE* fout = fopen("aib.out", "w");
	int N, M;

	fscanf(fin, "%d %d", &N, &M);

	vector<int> numbers;
	while (N-- > 0) {
		int x; fscanf(fin, "%d", &x);
		numbers.push_back(x);
	}

	SearchFenwickTree t{ numbers };

	answer(
		t,
		M,
		fin,
		fout
	);
	

	fclose(fin), fclose(fout);
}



int main() {
	solve();
}