#include <bits/extc++.h>

using namespace std;

constexpr long long inf = (long long)1e18 + 7;

constexpr int maxn = 4e5 + 5;

vector<int> g[maxn];

int used[maxn];

int t = 0;

void dfs(int v) {
    used[v] = t;
    for (auto u : g[v]) {
        if (used[u] < t) {
            dfs(u);
        }
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<long long> pr_sum(n + 1);
    map<int, vector<int>> pos;
    pos[0].push_back(0);
    for (int i = 0; i < n; ++i) {
        pr_sum[i + 1] = pr_sum[i] + a[i];
        pos[pr_sum[i + 1]].push_back(i + 1);
    }
    vector<pair<int, int>> qs(q);
    vector<long long> ans(q);
    vector<vector<int>> qs_ind(n + 1);
    for (int i = 0; i < q; ++i) {
        int tp;
        cin >> tp;
        cin >> qs[i].first >> qs[i].second;
        qs[i].first--;
        qs_ind[qs[i].second].push_back(i);
    }
    for (int i = 0; i < n + 1; ++i) {
        g[i + n + 1].push_back(i);
    }
    for (auto [vl, p] : pos) {
        for (int i = 1; i < (int)p.size(); ++i) {
            g[p[i] + n + 1].push_back(p[i - 1] + n + 1);
        }
    }
    for (int vl = 20; vl >= 0; --vl) {
        for (int i = 0; i < n + 1; ++i) {
            long long val1 = pr_sum[i] - vl;
            int p = lower_bound(pos[val1].begin(), pos[val1].end(), i) - pos[val1].begin() - 1;
            if (p != -1) {
                g[i].push_back(pos[val1][p] + n + 1);
            }
            val1 = pr_sum[i] + vl;
            p = lower_bound(pos[val1].begin(), pos[val1].end(), i) - pos[val1].begin() - 1;
            if (p != -1) {
                g[i].push_back(pos[val1][p] + n + 1);
            }
        }
        for (auto [_, p] : pos) {
            t++;
            for (auto ind : p) {
                dfs(ind);
                for (auto id : qs_ind[ind]) {
                    if (used[qs[id].first] == t) {
                        ans[id] = max(ans[id], (long long)vl);
                    }
                }
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}