#include <bits/stdc++.h>
using namespace std;
// https://space.bilibili.com/672346917

#ifndef LOCAL
#define LOG(...) 42
#endif

#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long LL;
typedef pair <int, int> PII;

constexpr double EPS = 1e-8;
const double PI = acos(-1);
constexpr LL inf = 1e18;

template <typename T = long long>
struct SegTree {
#define gao(x) u.x = max(l.x, r.x)
    struct node {
        int l, r;
        LL ppnn = -inf, pnpn = -inf;
        // ++--  +-+-
        LL p = -inf, n = inf;
        LL pp = -inf, nn = -inf, pn = -inf, np = -inf;
        LL ppn = -inf, pnn = -inf, pnp = -inf, npn = -inf;
    };
    int n;
    vector <node> tr;
    vector <T> a;

    SegTree(int _n = 1): n(_n), tr((_n + 5) << 2), a(_n + 5) {}
    SegTree(int _n, const vector <T> &_a) : n(_n), tr((_n + 5) << 2), a(_a) {
        build(1, 1, n);
    }

    void init(int u, int r) {
        assert(1 <= r && r <= n);
        tr[u].p = a[r], tr[u].n = -a[r];
    }
    void pushup(node &u, node &l, node &r) {
        gao(pp); gao(nn); gao(pn); gao(np);
        gao(ppn); gao(pnn); gao(pnp); gao(npn);
        gao(ppnn); gao(pnpn);

        // one
        gao(p); gao(n);

        // two
        u.pp = max(u.pp, l.p + r.p);
        u.pn = max(u.pn, l.p + r.n);
        u.np = max(u.np, l.n + r.p);
        u.nn = max(u.nn, l.n + r.n);

        // three
        u.ppn = max({u.ppn, l.p + r.pn, l.pp + r.n});
        u.pnn = max({u.pnn, l.p + r.nn, l.pn + r.n});
        u.pnp = max({u.pnp, l.p + r.np, l.pn + r.p});
        u.npn = max({u.npn, l.n + r.pn, l.np + r.n});

        // four
        u.ppnn = max({u.ppnn, l.p + r.pnn, l.pp + r.nn, l.ppn + r.n});
        u.pnpn = max({u.pnpn, l.p + r.npn, l.pn + r.pn, l.pnp + r.n});
    }
#undef gao
    void pushdown(node &u, node &l, node &r) {
        
    }
    void modify(int u, int l, int r, LL c) {
        if(tr[u].l >= l && tr[u].r <= r) {
            
            return;
        }
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1, l, r, c);
        if(r > mid) modify(u << 1 | 1, l, r, c);
        pushup(u);
    }
    LL len(int &u) {
        return 1LL * tr[u].r - tr[u].l + 1;
    }
    LL len(node &u) {
        return 1LL * u.r - u.l + 1; 
    }
    void pushup(int u) {
        pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }
    void pushdown(int u) {
        pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }
    void build(int u, int l, int r) {
        tr[u].l = l, tr[u].r = r;
        if(l == r) {
            init(u, r);
            return;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
    node query(int u, int l, int r) {
        if(tr[u].l >= l && tr[u].r <= r) {
            return tr[u];
        }
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else {
            node res, left, right;
            left = query(u << 1, l, r);
            right = query(u << 1 | 1, l, r);
            pushup(res, left, right);
            return res;
        }
    }
};

int multi_cases = 1;

void A_SOUL_AvA () {
    int n, q;
    cin >> n >> q;

    vector <LL> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] *= a[i];
    }

    SegTree <LL> st(n, a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        auto node = st.query(1, l, r);
        cout << max(node.ppnn, node.pnpn) << endl;
    }
}

int main () {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int T = 1;
    for (multi_cases && cin >> T; T; T--) {
        A_SOUL_AvA ();
    }

    return 0;
}