// http://infoarena.ro/problema/aib
#include <fstream>
#include <algorithm>
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);
int query(int right);
int search(int position);

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";
				break;
			case 2:
				toBeFound = first;
				out << search(lenght/2) << "\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 position) {
	int found = query(position);

	if(found > toBeFound)
		return search(position/2);
	else
		if(found < toBeFound)
			return search(position + (lenght-position+1) / 2);
		else
			if(position == 0 || position >lenght)
				return -1;
}