#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;

const string file = "aib";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;

int N;
int M;
vector<int> Aib;

inline int zeros(int x)
{
	return (x ^ (x - 1)) & x;
}

void update(int x, int v)
{
	for(int i = x; i <= N; i += zeros(i))
	{
		Aib[i] += v;
	}
}

int query(int x)
{
	int r = 0;
	for(int i = x; i > 0; i -= zeros(i))
	{
		r += Aib[i];
	}
	return r;
}

int search(int x)
{
	int step;
	for(step = 1; step < N; step <<= 1);
	for(int i = 0; step; step >>= 1)
	{
		if( i + step <= N)
		{
			if(x >= Aib[i+step])
			{
				i += step;
				x -= Aib[i];
				if(x == 0)
					return i;
			}
		}
	}
	return -1;
}

int main()
{
	fstream fout(outfile.c_str(), ios::out);
	fstream fin(infile.c_str(), ios::in);
	fin >> N >> M;
	Aib.resize(N + 1);
	for(int i = 0; i < N; i++)
	{
		int x;
		fin >> x;
		update(i + 1, x);
	}


	for(int i = 0; i < M; i++)
	{
		int op;
		int a, b;
		fin >> op;
		
		if(op == 0)
		{
			fin >> a >> b;
			update(a, b);
		}
		else if(op == 1)
		{
			fin >> a >> b;
			fout << query(b) - query(a - 1) << "\n";
		}
		else if(op == 2)
		{
			fin >> a;
			fout << search(a) << "\n";;
		}

	}

	fin.close();
	fout.close();
}