#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T, size_t N>
void re(array <T, N>& x);
template <class T> 
void re(vt <T>& x);

template <class T> 
void re(T& x) {
    cin >> x;
}

template <class T, class... M> 
void re(T& x, M&... args) {
    re(x); re(args...);
}

template <class T> 
void re(vt <T>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void re(array <T, N>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void wr(array <T, N> x);
template <class T> 
void wr(vt <T> x);

template <class T> 
void wr(T x) {
    cout << x;
}

template <class T, class ...M>  void wr(T x, M... args) {
    wr(x), wr(args...);
}

template <class T> 
void wr(vt <T> x) {
    for(auto it : x)
        wr(it, ' ');
}

template <class T, size_t N>
void wr(array <T, N> x) {
    for(auto it : x)
        wr(it, ' ');
}


inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

struct BIT {
    int n;
    vt <int> t;

    BIT() {}
    BIT(int _n) {
        n = _n;
        t.resize(n + 10);
    }

    void init(int _n) {
        n = _n;
        t.resize(n + 10);
    }

    void build(const vt <int>& a) {
        for (int i = 0; i < n; ++i)
            t[i + 1] = a[i];

        for (int i = 1; i <= n; ++i) {
            int p = i + (i & -i);
            if (p <= n) {
                t[p] = t[p] + t[i];
            }
        }
    }

    void upd(int idx, int add) {
        for (;idx <= n; idx += (idx & -idx))
            t[idx] += add;
    }

    ll query(int idx) {
        ll sum = 0;
        for (; idx >= 1; idx -= (idx & -idx))
            sum += t[idx];
        return sum;
    }

    ll query(int l, int r)  {
        return query(r) - query(l - 1);
    }

    int kth(ll target) {
        int l = 1, r = n;
        while (l <= r) {
            int m = l + (r - l) / 2;

            if (query(m) == target) {
                return m;
            }

            if (query(m) > target)  {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return -1;
    } 

};

void solve() {
    /* standard algorithm */
    int n, q; re(n, q);
    vt <int> a(n); re(a);
    BIT T(n);
    T.build(a);

    for (int i = 0; i < q; ++i) {
        int task; re(task);
        if (task == 0) {
            int a, b; re(a, b);
            T.upd(a, b);
            continue;
        }
        if (task == 1) {
            int a, b; re(a, b);
            wr(T.query(a, b), '\n');
            continue;
        }

        ll a; re(a);
        wr(T.kth(a), '\n');
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("aib");

    int t = 1;
    for(;t;t--) {
        solve();
    }
    
    return 0;
}