// http://infoarena.ro/problema/aib
#include <fstream>
using namespace std;

#define maxSize 100002
#define zeros(x) ( (x ^ (x - 1)) & x )

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

int lenght,toBeFound;
int AIB[maxSize];

void add(int location,int value);	// aduna la pozitia "location" valoarea "value"
int query(int right);	// returneaza suma elementelor sumsecventei [1,right]
int search(int left,int right);	// cautare binara

int main() {
	int nrOperations,value;
	int operationType,first,second;

	in >> lenght >> nrOperations;

	for(int i=1;i<=lenght;i++) {
		in >> value;
		add(i,value);
	}

	for(int i=1;i<=nrOperations;i++) {
		in >> operationType >> first;

		switch(operationType) {
			case 0:	
				in >> second;
				add(first,second);
				break;
			case 1:
				in >> second;
				out << query(second) - query(first-1) << "\n";	// suma elementelor din intervalul [first,second]
				break;
			case 2:
				toBeFound = first;	// toBeFound e variabila globala (necesara functiei search())
				out << search(1,lenght) << "\n";
				break;
		}
	}

	in.close();
	out.close();

	return (0);
}

void add(int location,int value) {
	for(int k=location;k<=lenght;k=k+zeros(k))
		AIB[k] = AIB[k] + value;
}

int query(int right) {
	int value = 0;

	for(int k=right;k>0;k=k-zeros(k))
		value = value + AIB[k];

	return value;
}

int search(int left,int right) {
    if(left > right)
		return -1;
	else {
		int middle = (left + right) / 2;
		int answer = query(middle);

		if(answer == toBeFound)
			return middle;
		else
			if(answer < toBeFound)
				return search(middle+1,right);
			else
				return search(left,middle-1);
	}
}