# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define db long double
# define scn(x) scanf("%I64d",&x)
# define scan(x) scanf("%d",&x)
# define print(x) printf("%d ",x)
# define prnt(x) printf("%I64d ",x);
# define eol printf("\n")
# define IOS ios_base :: sync_with_stdio(0)
# define pe "Possible"
# define ie "Impossible"
# define halt(...) {printf(__VA_ARGS__);eol;exit(0);}
# define rep(n) for (int qwerty = 1;qwerty <= n;++qwerty)
# define pp(n) cerr << #n << " = " << n << '\n'
# define ppp(v) for (auto it : v) cerr << it << ' ';cerr << '\n'
const int mod = 1e9 + 7;
int s[1 << 20];
int main(void)
{
    int n,m;
    ifstream fi("aib.in");
    ofstream fo("aib.out");
    IOS;
    fi>>n>>m;
    auto upd = [&](int i,int val)
    {
        for (;i <= n;i += i&(-i)) s[i] += val;
    };
    auto query = [](int i)
    {
        int ans = 0;
        for (;i;i -= i&(-i)) ans += s[i];
        return ans;
    };
    auto bin = [&](int k)
    {
        if (query(n) < k) return -1;
        int ans = 0;
        for (int with = 1 << 16;with;with /= 2)
            if (ans + with <= n && query(ans + with) < k) ans += with;
        return (query(++ans) == k ? ans : -1);
    };
    int val;
    for (int i = 1;i <= n;++i) fi>>val,upd(i,val);
    while (m --)
    {
        int op,l,r;
        fi>>op;
        if (!op) fi>>l>>r,upd(l,r);
        else
        if (op == 1) fi>>l>>r,fo << query(r) - query(l - 1) << '\n';
        else fi>>l,fo << bin(l) << '\n';
    }
    return 0;
}