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

int n;
int vect_aib[100001];

void update(int, const int&);
int query(int);
int bSearch(const int&, int, int);


int main(void) {
	int m;
	ifstream fin("aib.in");
	fin >> n >> m;
	
	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 << query(max(x,y)) - query(min(x,y)-1) << '\n';
		}
		if(op == 2) {
			fout << bSearch(x, 1, n)  << '\n';
		}
	}
	fin.close();
	fout.close();
}


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

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

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