#include<bits/stdc++.h>

#define lx (x<<1)
#define rx (x<<1|1)
#define mid ((l+r)>>1)

using namespace std;

typedef long long LL;

const int maxn = 2e5 + 10;
const LL inf =1ll<<60;

LL st0[maxn << 2][5][5];
LL st1[maxn << 2][5][5];
LL a[maxn];
int n,q;

void build_st(int x,int l,int r)
{
    if (l==r)
    {
        int i,j;
        for(i=0;i<5;i++)
            for(j=0;j<5;j++)
            {
                if (i!=j)
                {
                    st0[x][i][j]=-inf;
                    st1[x][i][j]=-inf;
                }
            }
        
        st0[x][0][1]=a[l];
        st0[x][1][2] = a[l];
        st0[x][2][3] = -a[l];
        st0[x][3][4] = -a[l];

        st1[x][0][1] = a[l];
        st1[x][1][2] = -a[l];
        st1[x][2][3] = a[l];
        st1[x][3][4] = -a[l];
    }else {
        build_st(lx,l,mid);
        build_st(rx,mid+1,r);

        int i,j,k;
        for(i=0;i<5;i++)
            for(j=i;j<5;j++)
            {
                st0[x][i][j]=st1[x][i][j]=-inf;
                for(k=i;k<=j;k++)
                {
                    st0[x][i][j]=max(st0[x][i][j],st0[lx][i][k]+st0[rx][k][j]);
                    st1[x][i][j] = max(st1[x][i][j], st1[lx][i][k] + st1[rx][k][j]);
                }
            }
    }
}

void standing_by()
{
    int i;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++) 
    {
        scanf("%lld",&a[i]);
        a[i]=a[i]*a[i];
    }
    build_st(1,1,n);
}

LL ans0[5],ans1[5];
LL tmp0[5],tmp1[5];

void mul_st(int x,int l,int r,int L,int R)
{
    if (r<L||l>R) return;
    if (l>=L&&r<=R)
    {
        int i,j;
        for(i=0;i<5;i++)
        {
            tmp0[i]=tmp1[i]=-inf;
            for(j=0;j<=i;j++)
            {
                tmp0[i] = max(tmp0[i],ans0[j]+st0[x][j][i]);
                tmp1[i] = max(tmp1[i], ans1[j] + st1[x][j][i]);
            }
        }
        for(i=0;i<5;i++)
        {
            ans0[i]=tmp0[i];
            ans1[i]=tmp1[i];
        }
    }else {
        mul_st(lx,l,mid,L,R);
        mul_st(rx,mid+1,r,L,R);
    }
}

void complete()
{
    int L,R;
    int i;
    LL ans;
    for(;q;q--)
    {
        scanf("%d%d",&L,&R);
        ans0[0]=ans1[0]=0;
        for(i=1;i<=4;i++)
            ans0[i]=ans1[i]=-inf;
        mul_st(1,1,n,L,R);
        ans=max(ans0[4],ans1[4]);
        printf("%lld\n",ans);
    }
}

int main()
{
#ifdef TanJI
    clock_t c1 = clock();
    freopen("D:\\Cpp\\1.in", "r", stdin);
    freopen("D:\\Cpp\\1.out", "w", stdout);
#endif
    int t;
    scanf("%d",&t);
    for(;t;t--)
    {
        standing_by();
        complete();
    }
    return 0;
}