#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
#define int long long
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mxn=2e5+5;
/*
ABAB
AABB
*/
struct node
{
	int A,B,AA,BB,AAB,ABB,ABA,BAB,AB,BA,ans;
	friend node operator +(const node &x,const node &y)
	{
		node res;
		res.A=max(x.A,y.A);
		res.B=max(x.B,y.B);
		res.AA=max({x.AA,y.AA,x.A+y.A});
		res.BB=max({x.BB,y.BB,x.B+y.B});
		res.AAB=max({x.AAB,y.AAB,x.AA+y.B,x.A+y.AB});
		res.ABB=max({x.ABB,y.ABB,x.AB+y.B,x.A+y.BB});
		res.ABA=max({x.ABA,y.ABA,x.AB+y.A,x.A+y.BA});
		res.BAB=max({x.BAB,y.BAB,x.BA+y.B,x.B+y.AB});
		res.AB=max({x.AB,y.AB,x.A+y.B});
		res.BA=max({x.BA,y.BA,x.B+y.A});
		res.ans=max({x.ans,y.ans,x.A+y.BAB,x.AB+y.AB,x.ABA+y.B,x.A+y.ABB,x.AA+y.BB,x.AAB+y.B});
		return res;
	}
	void add(int a,int b)
	{
		A=a,B=b;
		AA=BB=AAB=ABB=ABA=BAB=AB=BA=ans=-1e17;
	}
};
struct seg
{
	int l,r;
	node s;
}t[mxn*4];
#define ls w<<1
#define rs ls|1
int a[mxn];
void build(int w,int l,int r)
{
	t[w].l=l,t[w].r=r;
	if(l<r)
	{
		int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		t[w].s=t[ls].s+t[rs].s;
	}
	else t[w].s.add(a[l]*a[l],-a[l]*a[l]);
}
node ask(int w,int l,int r)
{
	if(t[w].l>=l&&t[w].r<=r) return t[w].s;
	if(t[ls].r>=l&&t[rs].l<=r) return ask(ls,l,r)+ask(rs,l,r);
	return ask(t[ls].r>=l?ls:rs,l,r);
}
signed main()
{
	int T=read();
	while(T--)
	{
		int n=read(),m=read(),i,j;
		for(i=1;i<=n;i++)
			a[i]=read();
		build(1,1,n);
		while(m--)
		{
			int l=read(),r=read();
			printf("%lld\n",ask(1,l,r).ans);
		}
	}
}