#include <fstream>
#include <vector>
//#include <algorithm>
using namespace std;


vector <int>  vect_aib;


void update(int, int);
int query(int);

int bSearch(int, int, int);

inline int val_query(int, int);
inline int max_query(int);


int main(void) {
	int n, m;
	ifstream fin("aib.in");
	fin >> n >> m;
	vect_aib.resize(n+1, 0);
	
	int val;
	for(int i = 1; i <= n; ++i) {
		fin >> val;
		update(i, val);
	}
	
	int op, x, y;
	ofstream fout("aib.out");
	for(int i = 1; i <= m; ++i) {
		fin >> op >> x;
		if(op == 0) {
			fin >> y;
			update(x, y);
		}
		if(op == 1) {
			fin >> y;
			fout << val_query(x, y) << '\n';
		}
		if(op == 2)
			fout << max_query(x) << '\n';
	}
	fin.close();
	fout.close();
}


inline int val_query(int x, int y) {
	return query(y) - query(x-1);
}

inline int max_query(int x) {
	return bSearch(x, 1, vect_aib.size()-1);
}


int query(int x) {
	int sum = 0;
	while(x > 0) {
		sum += vect_aib[x];
		x -= (x & -x);
	}
	return sum;
}

void update(int x, int y) {
	int s = vect_aib.size();
	while(x < s) {
		vect_aib[x] += y;
		x += (x & -x);
	}
}

int bSearch(int sum, int x, int y) {
	int mij, val_mij;
	while(x <= y) {
		mij = (x + y) / 2;
		val_mij = query(mij);
		
		if(val_mij == sum)
			return mij;
		if(sum < val_mij)
			y = mij - 1;
		else
			x = mij + 1;
	}
	return -1;
}