#include <fstream>

using namespace std;

class InParser{
private:
		FILE* fin;
		char* buff;
		int sp;

		char read_ch(){
			++sp;
			if(sp == 16 * 1024){
				sp = 0;
				fread(buff, 1, 16 * 1024, fin);
			}
			return buff[sp];
		}

public:
		InParser(const char* nume){
			fin = fopen(nume, "r");
			buff = new char[16 * 1024]();
			sp = 16 * 1024 - 1;
		}

		InParser& operator>>(int& n){
			char c;
			while(!isdigit(c = read_ch()) && c != '-');
			int sgn = 1;
			if(c == '-'){
				n = 0;
				sgn = -1;
			}else{
				n = c - '0';
			}
			while(isdigit(c = read_ch())){
				n = 10 * n + c - '0';
			}
			n *= sgn;
			return *this;
		}

		InParser& operator>>(long long& n){
			char c;
			n = 0;
			while(!isdigit(c = read_ch()) && c != '-');
			long long sgn = 1;
			if(c == '-'){
				n = 0;
				sgn = -1;
			}else{
				n = c - '0';
			}
			while(isdigit(c = read_ch())){
				n = 10 * n + c - '0';
			}
			n *= sgn;
			return *this;
		}
};

class OutParser{
private:
		FILE* fout;
		char* buff;
		int sp;

		void write_ch(char ch){
			if(sp == 64 * 1024){
				fwrite(buff, 1, 64 * 1024, fout);
				sp = 0;
				buff[sp++] = ch;
			}else{
				buff[sp++] = ch;
			}
		}


public:
		OutParser(const char* name){
			fout = fopen(name, "w");
			buff = new char[64 * 1024]();
			sp = 0;
		}

		~OutParser(){
			fwrite(buff, 1, sp, fout);
			fclose(fout);
		}

		OutParser& operator<<(int vu32){
			if(vu32 <= 9){
				write_ch(vu32 + '0');
			}else{
				(*this) << (vu32 / 10);
				write_ch(vu32 % 10 + '0');
			}
			return *this;
		}

		OutParser& operator<<(long long vu64){
			if(vu64 <= 9){
				write_ch(vu64 + '0');
			}else{
				(*this) << (vu64 / 10);
				write_ch(vu64 % 10 + '0');
			}
			return *this;
		}

		OutParser& operator<<(char ch){
			write_ch(ch);
			return *this;
		}

		OutParser& operator<<(const char* ch){
			while(*ch){
				write_ch(*ch);
				++ch;
			}
			return *this;
		}
};

InParser fin("aib.in");
OutParser fout("aib.out");

const int N_MAX = 1e5;
const int FENWICK_TREE_DIM_MAX = N_MAX + 1;
const int LOG_MAX = 16;

template<typename T>
class FenwickTree{
private:
		T bit[FENWICK_TREE_DIM_MAX]{};
		int bitSize;

		inline T leastSignificantBit(int i){
			return i & (-i);
		}

public:
		void build(int n, InParser& fin){
			bitSize = n;

			T x;
			for(int i = 1; i <= n; ++i){
				fin >> x;
				bit[i] += x;

				if(i + leastSignificantBit(i) <= bitSize)
					bit[i + leastSignificantBit(i)] += bit[i];
			}
		}

		void update(int pos, T val){
			while(pos <= bitSize){
				bit[pos] += val;
				pos += leastSignificantBit(pos);
			}
		}

		T query(int pos){
			T sum = 0;

			while(pos > 0){
				sum += bit[pos];
				pos -= leastSignificantBit(pos);
			}

			return sum;
		}

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

		int find(T val){
			int pos = 0;
			T sum{};

			for(int e = LOG_MAX; e >= 0; --e)
				if(pos + (1 << e) <= bitSize && sum + bit[pos + (1 << e)] < val){
					pos += 1 << e;
					sum += bit[pos];
				}

			if(pos + 1 <= bitSize && query(pos + 1) == val)
				++pos;
			else
				pos = -1;

			return pos;
		}

		void print(){
			for(int i = 0; i <= bitSize; ++i)
				fout << bit[i] << ' ';
			fout << '\n';
		}
};

FenwickTree<int> bit;

int main(){
	int n, queries;
	fin >> n >> queries;

	bit.build(n, fin);

	int type, a, b;
	for(int i = 0; i < queries; ++i){
		fin >> type;
		if(!type){
			fin >> a >> b;
			bit.update(a, b);
		}else if(type == 1){
			fin >> a >> b;
			fout << bit.query(a, b) << '\n';
		}else{
			fin >> a;
			fout << bit.find(a) << '\n';
		}
	}

	return 0;
}