#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned ll
#define vec vector
#define flist forward_list
#define um unordered_map
#define us unordered_set
#define all(x) x.begin(), x.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define ld long double

#define LL_MAX LLONG_MAX
#define LL_MIN LLONG_MIN
#define LD_MAX LDBL_MAX
#define LD_MIN LDBL_MIN

#define nline '\n'

#define vv(type, name, n, ...) vector<vector<type>> name(n, vector<type>(__VA_ARGS__))
#define vvv(type, name, n, m, ...)                                                                                     \
    vector<vector<vector<type>>> name(n, vector<vector<type>>(m, vector<type>(__VA_ARGS__)))

#define for1(n) for (ll i = 0; i < (ll)(n); ++i)
#define for2(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define for4(i, a, b, c) for (ll i = (ll)(a); i < (ll)(b); i += (c))
#define for1e(n) for (ll i = 1; i <= (ll)(n); ++i)
#define for2e(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define for3e(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define for4e(i, a, b, c) for (ll i = (ll)(a); i <= (ll)(b); i += (c))
#define forit(v) for (auto it = v.begin(); it != v.end(); it++)
#define forit2(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define forrit(v) for (auto it = v.rbegin(); it != v.rend(); it++)
#define forrit2(it, v) for (auto it = v.rbegin(); it != v.rend(); it++)

const ld margin = 0.000001;
const ll MOD = 1e9 + 7;
const ld pi = acos(-1);

ld acot(ld x);
int cmpD(ld x, ld y);

class Real
{
public:
    ld val;

    Real();
    Real(const double x);
    operator double() const;
    template<class T> void operator=(const T x);
    template<class T> bool operator==(const T x) const;
    template<class T> bool operator<(const T x) const;
    template<class T> bool operator<=(const T x) const;
    template<class T> bool operator>(const T x) const;
    template<class T> bool operator>=(const T x) const;
    template<class T> void operator+=(const T x);
    template<class T> void operator-=(const T x);
    template<class T> void operator*=(const T x);
    template<class T> void operator/=(const T x);
    template<class T> Real operator+(const T x) const;
    template<class T> Real operator-(const T x) const;
    template<class T> Real operator*(const T x) const;
    template<class T> Real operator/(const T x) const;
};
Real operator"" _r(long double x);
istream& operator>>(istream& is, Real& x);

template<class type, class typeHash = hash<type>>
class DisjointSets
{
private:
	um<type, ll, typeHash> father_, size_;
	ll treeCount_;
	
public:
	DisjointSets();
	void unite(type a, type b);
	type father(type node);
	ll treeSize(type node);
	ll size();
	void insert(type val);
	ll treeCount();
	bool contains(type val);
};

const string FILENAME = "aib";
ifstream fin(FILENAME + ".in");
ofstream fout(FILENAME + ".out");

#define cin fin
#define cout fout

void solve();
void updateAib(vec<ll>& aib, ll pos, ll val)
{
	while(pos < aib.size())
	{
		aib[pos] += val;
		pos += pos & (-pos);		
	}
}
ll prefAib(vec<ll>& aib, ll pos)
{
	ll sum = 0;
	
	while(pos >= 1)
	{
		sum += aib[pos];
		pos -= pos & (-pos);
	}
	
	return sum;
}
ll searchPos(vec<ll>& aib, ll val)
{
	ll pos = 0, step = 1;
	
	while(step < aib.size())
		step <<= 1;
	step >>= 1;
	
	while(step >= 1)
	{
		if(pos + step < aib.size() && aib[pos + step] <= val)
		{
			pos += step;
			val -= aib[pos];
			
			if(val == 0)
			{
				return pos;
			}
		}
		
		step >>= 1;
	}
	
	return -1;
}

int main()
{
	ll n, m;
	
	cin >> n >> m;
	
	vec<ll> nums(n + 1), aib(n + 1, 0);
	
	for1e(n)
	{
		cin >> nums[i];
	}
	
	for1e(n)
	{
		ll index = i;
		
		aib[index] += nums[i];
		
		if(index + (index & (-index)) <= n)
		{
			aib[index + (index & (-index))] += aib[index];
		}
		
		index += index & (-index);
	}
	
	for1(m)
	{
		ll type, a, b;
		
		cin >> type;
		
		if(type == 0)
		{
			cin >> a >> b;
			
			updateAib(aib, a, b);
		}
		else if(type == 1)
		{
			cin >> a >> b;
			
			cout << prefAib(aib, b) - prefAib(aib, a - 1) << nline;
		}
		else
		{
			cin >> a;
			
			cout << searchPos(aib, a) << nline;
		}
	}
	
    return 0;
}

void solve()
{
}


Real::Real()
{

}
Real::Real(const double x)
{
    this->val = x;
}
Real::operator double() const
{
    return this->val;
}
template<class T> void Real::operator=(const T x)
{
    this->val = x;
}
template<class T> bool Real::operator==(const T x) const
{
    return cmpD(this->val, x) == 0;
}
template<class T> bool Real::operator<(const T x) const
{
    return cmpD(this->val, x) < 0;
}
template<class T> bool Real::operator<=(const T x) const
{
    return cmpD(this->val, x) <= 0;
}
template<class T> bool Real::operator>(const T x) const
{
    return cmpD(this->val, x) > 0;
}
template<class T> bool Real::operator>=(const T x) const
{
    return cmpD(this->val, x) >= 0;
}
template<class T> void Real::operator+=(const T x)
{
	this->val += x;
}
template<class T> void Real::operator-=(const T x)
{
	this->val -= x;
}
template<class T> void Real::operator*=(const T x)
{
	this->val *= x;
}
template<class T> void Real::operator/=(const T x)
{
	this->val /= x;
}
template<class T> Real Real::operator+(const T x) const
{
	return (Real)(this->val + x);
}
template<class T> Real Real::operator-(const T x) const
{
	return (Real)(this->val - x);
}
template<class T> Real Real::operator*(const T x) const
{
	return (Real)(this->val * x);
}
template<class T> Real Real::operator/(const T x) const
{
	return (Real)(this->val / x);
}
Real operator"" _r(long double x)
{
    return Real(x);
}
istream& operator>>(istream& is, Real& x)
{
    is >> x.val;
    return is;
}
int cmpD(ld x, ld y)
{
    if(abs(x - y) < margin)
        return 0;
    
    if(x - y < margin)
        return -1;
    
    return 1;
}
template<class type, class typeHash>
DisjointSets<type, typeHash>::DisjointSets()
{
	this->treeCount_ = 0;
}
template<class type, class typeHash>
void DisjointSets<type, typeHash>::unite(type a, type b)
{
	if(this->size_.find(a) == this->size_.end() || this->size_.find(b) == this->size_.end())
	{
		cerr << "INVALID DSU UNITE" << nline;
		exit(0);	
	}
	
	ll repA, repB;
	repA = this->father(a);
	repB = this->father(b);
	
	if(repA == repB)
		return;
	
	if(this->size_[repA] < this->size_[repB])
	{
		this->father_[repA] = repB;
		this->size_[repB] += this->size_[repA];
	}
	else
	{
		this->father_[repB] = repA;
		this->size_[repA] += this->size_[repB];
	}
	
	this->treeCount_--;
}
template<class type, class typeHash>
type DisjointSets<type, typeHash>::father(type node)
{
	if(this->size_.find(node) == this->size_.end())
	{
		cerr << "INVALID DSU FATHER" << nline;
		exit(0);	
	}
	
	if(this->father_.find(node) == this->father_.end())
	{
		return node;
	}
	
	return this->father_[node] = this->father(this->father_[node]);
}
template<class type, class typeHash>
ll DisjointSets<type, typeHash>::treeSize(type node)
{
	if(this->size_.find(node) == this->size_.end())
	{
		cerr << "INVALID DSU TREESIZE" << nline;
		exit(0);	
	}
	
	return this->size_[this->father(node)];
}
template<class type, class typeHash>
ll DisjointSets<type, typeHash>::size()
{
	return this->size_.size();
}
template<class type, class typeHash>
void DisjointSets<type, typeHash>::insert(type val)
{
	if(this->size_.find(val) != this->size_.end())
	{
		return;	
	}
	
	this->size_[val] = 1;
	this->treeCount_++;
}
template<class type, class typeHash>
ll DisjointSets<type, typeHash>::treeCount()
{
	return this->treeCount_;
}
template<class type, class typeHash>
bool DisjointSets<type, typeHash>::contains(type val)
{
	return this->size_.find(val) != this->size_.end();
}
ld acot(ld x)
{
	return pi / 2 - atan(x);
}