#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5 + 50;
const ll inf = 1e18;

int T, n, m, a[N];

#define ls (x << 1) 
#define rs (x << 1 | 1)

struct node {
    int l, r;
    ll lef, rig, a, b, c, d;
    ll e, f, g, h, i, j;
    node () {
        lef = rig = a = b = c = d = -inf;
        e = f = g = h = i = j = -inf;
    }
}t[N << 2];

node operator + (node x, node y) {
    node res;
    res.lef = max (res.lef, x.lef);
    res.lef = max (res.lef, y.lef);
    res.lef = max (res.lef, x.a + y.f);
    res.lef = max (res.lef, x.c + y.d);
    res.lef = max (res.lef, x.e + y.b);

    res.rig = max (res.rig, x.rig);
    res.rig = max (res.rig, y.rig);
    res.rig = max (res.rig, x.a + y.i);
    res.rig = max (res.rig, x.g + y.g);
    res.rig = max (res.rig, x.h + y.b);

    res.i = max (res.i, x.i);
    res.i = max (res.i, y.i);
    res.i = max (res.i, x.b + y.g);
    res.i = max (res.i, x.j + y.b);

    res.h = max (res.h, x.h);
    res.h = max (res.h, y.h);
    res.h = max (res.h, x.a + y.j);
    res.h = max (res.h, x.g + y.a);
    
    res.f = max (res.f, x.f);
    res.f = max (res.f, y.f);
    res.f = max (res.f, x.g + y.b);
    res.f = max (res.f, x.a + y.d);

    res.e = max (res.e, x.e);
    res.e = max (res.e, y.e);
    res.e = max (res.e, x.a + y.g);
    res.e = max (res.e, x.c + y.b);

    res.j = max (res.j, x.j);
    res.j = max (res.j, y.j);
    res.j = max (res.j, x.b + y.a);

    res.g = max (res.g, x.g);
    res.g = max (res.g, y.g);
    res.g = max (res.g, x.a + y.b);

    res.c = max (res.c, x.c);
    res.c = max (res.c, y.c);
    res.c = max (res.c, x.a + y.a);

    res.d = max (res.d, x.d);
    res.d = max (res.d, y.d);
    res.d = max (res.d, x.b + y.b);

    res.a = max (res.a, x.a);
    res.a = max (res.a, y.a);

    res.b = max (res.b, x.b);
    res.b = max (res.b, y.b);

    return res;
}

void pushup (int x) {
    t[x] = t[ls] + t[rs];
    t[x].l = t[ls].l, t[x].r = t[rs].r;
}

void build (int l, int r, int x = 1) {
    t[x] = node ();
    t[x].l = l, t[x].r = r;
    if (l == r) {
        t[x].a = (ll)a[l] * a[l];
        t[x].b = (ll)-a[l] * a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build (l, mid, ls), build (mid + 1, r, rs);
    pushup (x);
}

node query (int l, int r, int x = 1) {
    if (l <= t[x].l && t[x].r <= r) 
        return t[x];

    int mid = (t[x].l + t[x].r) >> 1;
    node res;
    if (l <= mid) res = res + query (l, r, ls);
    if (r >  mid) res = res + query (l, r, rs);
    return res;
}

int main() {
#ifdef LOCAL
    clock_t c1 = clock();
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    // ===================================================    
    scanf ("%d", &T);
    while (T --) {
        scanf ("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++) 
            scanf ("%d", &a[i]);
        
        build (1, n);

        cerr << t[1].l << ' ' << t[1].r << endl;

        while (m --) {
            int l, r; scanf ("%d%d", &l, &r);
            node ans = query (l, r);
            printf("%lld\n", max (ans.lef, ans.rig));
        }
    }
    // ===================================================    
#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" << endl;
#endif
    return 0;
}