#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 100005

struct interv
{
	interv(int stS, int drS, int sumS): st(stS), dr(drS), sum(sumS)
	{
	}
	interv():st(0), dr(0), sum(0)
	{
	}
	void operator=(interv interv2)
	{
		st = interv2.st;
		dr = interv2.dr;
		sum = interv2.sum;
	}
	inline void schimba(int stS, int drS, int sumS)
	{
		st = stS; dr = drS; sum = sumS;
	}
	inline void adaugaLaVal(int deAdaugat)
	{
		sum += deAdaugat;
	}
	int st, dr, sum;
};

interv noduri[MAXN];
vector<int> arb[MAXN];

int indiceDeAdaugat, valDeAdaugat, nrNoduri;
void adaugaDFS(int nodCurent);
void afisArb(int nodCurent);
void adauga(int indiceDeAdaugatS, int valDeAdaugatS)
{
	indiceDeAdaugat = indiceDeAdaugatS;
	valDeAdaugat = valDeAdaugatS;
	adaugaDFS(0); // !!! ??? cauta locul urmatoarei adaugari in arbore si o pune unde trebuie
	//afisArb(0);
	//cout << '\n';
}

void adaugaDFS(int nodCurent)
{
	if(noduri[nodCurent].st == noduri[nodCurent].dr && noduri[nodCurent].st != 0) //interval cu un singur element
		if(indiceDeAdaugat == noduri[nodCurent].st) //avem de adaugat in nodul exact in nodul in care suntem
		{
			noduri[nodCurent].adaugaLaVal(valDeAdaugat);
			return;
		}
		else
		//cand initial avem un interval cu un singur element (de tipul [a,a]) si trebuie largit
		{
			nrNoduri++;
			arb[nodCurent].push_back(nrNoduri);
			noduri[nrNoduri] = noduri[nodCurent];
		}
	//modificarea dimensiunii intervalului curent daca e prea mititel
	if(noduri[nodCurent].st > indiceDeAdaugat || noduri[nodCurent].st == 0)
		noduri[nodCurent].st = indiceDeAdaugat;
	if(noduri[nodCurent].dr < indiceDeAdaugat || noduri[nodCurent].dr == 0)
		noduri[nodCurent].dr = indiceDeAdaugat;
	//se adauga la suma valorilor din interval
	noduri[nodCurent].adaugaLaVal(valDeAdaugat);
	if(noduri[nodCurent].st == noduri[nodCurent].dr)
		return;
	
	//daca nu are niciun fiu:
	if(arb[nodCurent].size() == 0)
	{
		nrNoduri++;
		arb[nodCurent].push_back(nrNoduri);
		noduri[nrNoduri].schimba(indiceDeAdaugat, indiceDeAdaugat, valDeAdaugat);
		return;
	}
	
	//daca intra intr-un interval fiu...
	vector<int>::iterator it;
	for(it = arb[nodCurent].begin(); it != arb[nodCurent].end(); it++)
		if(noduri[*it].st <= indiceDeAdaugat && noduri[*it].dr >= indiceDeAdaugat)
		{
			adaugaDFS(*it);
			return;
		}
	
	if(arb[nodCurent].size() == 1)
	//are un singur interval fiu in care nu intra, asa ca mai facem unul
	{
		nrNoduri++;
		//pentru a mentine sortati c8ii
		if(noduri[arb[nodCurent].front()].st > indiceDeAdaugat)
		{ //se adauga nodul la inceput daca e inaintea intervalului
			arb[nodCurent].push_back(arb[nodCurent].front());
			arb[nodCurent].front() = nrNoduri;
		}
		else
		{ //se adauga la sfarsit
			arb[nodCurent].push_back(nrNoduri);
		}
		noduri[nrNoduri].schimba(indiceDeAdaugat, indiceDeAdaugat, valDeAdaugat);
		return;
	}
	if(arb[nodCurent].size() == 2)
	//are 2 intervale fii, asa ca trebuie sa alegem in care dintre ele sa il punem
	{
		if(indiceDeAdaugat < noduri[arb[nodCurent].front()].st)
		//daca e inainte de primul, acolo il punem
			adaugaDFS(arb[nodCurent].front());
		else if(indiceDeAdaugat > noduri[arb[nodCurent].back()].dr)
		//e dupa ultimul, acolo il punem
			adaugaDFS(arb[nodCurent].back());
		else
		//e intre ele, il punem in primul
			adaugaDFS(arb[nodCurent].front());
	}
}

void afisArb(int nodCurent)
{
	cout << nodCurent << " [" << noduri[nodCurent].st << ',' << noduri[nodCurent].dr << "] " << noduri[nodCurent].sum << '\n';
	vector<int>::iterator it;
	for(it = arb[nodCurent].begin(); it != arb[nodCurent].end(); it++)
		afisArb(*it);
}

int stanga, dreapta, rez;
void calculSumaDFS(int nodCurent)
{
	if(noduri[nodCurent].st >= stanga && noduri[nodCurent].dr <= dreapta)
	//in acest if intra teoretic numai daca varful arborelui e inclus in interval
	{
		rez += noduri[nodCurent].sum;
		return;
	}
	vector<int>::iterator it;
	for(it = arb[nodCurent].begin(); it != arb[nodCurent].end(); it++)
		if(noduri[*it].st >= stanga && noduri[*it].dr <= dreapta)
		//intervalul `*it` se afla in interiorul lui [stanga,dreapta]: se creste rezultatul
			rez += noduri[*it].sum;
		else if((noduri[*it].st <  stanga && noduri[*it].dr <= dreapta) ||
				(noduri[*it].st >= stanga && noduri[*it].dr >  dreapta))
		//intervalul `*it` se intersecteaza cu intervalul [stanga,dreapta]: se intra inauntru
			calculSumaDFS(*it);
}

int calculSuma(int st, int dr)
//calculeaza suma din arbore din intervalul [st,dr]
{
	stanga = st;
	dreapta = dr;
	rez = 0;
	calculSumaDFS(0);
	return rez;
}

int sume[MAXN];
int main()
{
	int m, n;
	int i, op, a, b, st, dr, piv, sum;
	ifstream in("aib.in");
	ofstream out("aib.out");
	
	in >> n >> m;
	for(i = 1; i <= n; i++)
	{
		in >> sume[i];
		sume[i] += sume[i - 1];
	}
	
	for(i = 1; i <= m; i++)
	{
		in >> op;
		switch(op)
		{
		case 0:
			in >> a >> b;
			adauga(a, b);
			break;
		case 1:
			in >> a >> b;
			out << sume[b] - sume[a - 1] + calculSuma(a,b) << '\n';
			break;
		case 2:
			in >> a;
			//cautare binara dupa k astfel incat sume[k] + calculSuma(0, k) == a
			st = 1;
			dr = n;
			while(st <= dr)
			{
				piv = (st + dr) / 2;
				sum = sume[piv] + calculSuma(0, piv);
				if(sum == a)
					break;
				else
					if(sum > a)
						dr = piv - 1;
					else
						st = piv + 1;
			}
			if(sum != a)
				piv = -1;
			out << piv << '\n';
			break;
		default:
			cout << "EROARE";
		}
	}
}