#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=2e6+5;
const int inf=2e9+1;
int T,n,a[N];
int ans,mn,fl_del,fl_add,fl_nan;
signed main(){
    freopen("stone.in","r",stdin);
    freopen("stone.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        fo(i,1,n)scanf("%d",&a[i]);
        ans=0;mn=inf;
        fl_add=fl_del=fl_nan=0;
        fo(i,1,n){
            if(a[i]>0)fl_add++;
            else if(a[i]<0)fl_del++;
            else fl_nan++;
            ans=max(ans+a[i],ans-a[i]);
            mn=min(mn,abs(a[i]));
        }
        if(fl_nan)ans=ans;
        else if(!fl_del)ans-=2*mn;
        else if(!fl_add)ans-=2*mn;
        if(n==1)ans=a[1];
        printf("%d\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3e5+5;
int T,p,q,n,ans;
int xa[N],xb[N],ya[N],yb[N];
struct scan{
    int x,yl,yr,tp;
    scan(){}
    scan(int a,int b,int c,int d){x=a;yl=b;yr=c;tp=d;}
    bool operator < (scan a)const{
        return x<a.x; 
    }
}sca[N];
int lsh[N*2],lh;
struct XDS{
    #define ls x<<1
    #define rs x<<1|1
    int s1[N*8],t1[N*8],s2[N*8],t2[N*8],tg[N*8];
    void pushup(int x){
        if(t1[ls]==t1[rs]){
            t1[x]=t1[ls],s1[x]=s1[ls]+s1[rs];
            t2[x]=max(t2[ls],t2[rs]);s2[x]=0;
            if(t2[ls]==t2[x])s2[x]+=s2[ls];
            if(t2[rs]==t2[x])s2[x]+=s2[rs];
        }
        else if(t1[ls]>t1[rs]){
            t1[x]=t1[ls],s1[x]=s1[ls];
            t2[x]=max(t2[ls],t1[rs]);s2[x]=0;
            if(t2[ls]==t2[x])s2[x]+=s2[ls];
            if(t1[rs]==t2[x])s2[x]+=s1[rs];
        }
        else {
            t1[x]=t1[rs],s1[x]=s1[rs];
            t2[x]=max(t2[rs],t1[ls]);s2[x]=0;
            if(t2[rs]==t2[x])s2[x]+=s2[rs];
            if(t1[ls]==t2[x])s2[x]+=s1[ls];
        }
        return ;
    }
    void pushdown(int x){
        tg[ls]+=tg[x];tg[rs]+=tg[x];
        t1[ls]+=tg[x];t2[ls]+=tg[x];
        t1[rs]+=tg[x];t2[rs]+=tg[x];
        tg[x]=0;return ;
    }
    void build(int x,int l,int r){
        tg[x]=0;
        if(l==r){
            t1[x]=0;s1[x]=lsh[l+1]-lsh[l];
            t2[x]=-1;s2[x]=0;
            return ;
        }
        int mid=l+r>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(x);return ;
    }
    void ins(int x,int l,int r,int ql,int qr,int v){
        if(ql>qr)return ;
        if(ql<=l&&r<=qr){
            tg[x]+=v;t1[x]+=v;t2[x]+=v;
            return ;
        }
        if(tg[x])pushdown(x);
        int mid=l+r>>1;
        if(ql<=mid)ins(ls,l,mid,ql,qr,v);
        if(qr>mid)ins(rs,mid+1,r,ql,qr,v);
        pushup(x);return ;
    }
    #undef ls
    #undef rs
}xds;
signed main(){
    freopen("carpet.in","r",stdin);
    freopen("carpet.out","w",stdout);
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld",&p,&q,&n);ans=0;
        fo(i,1,n){
            scanf("%lld%lld%lld%lld",&xa[i],&ya[i],&xb[i],&yb[i]);
            lsh[i*2-1]=ya[i];lsh[i*2]=yb[i];
            sca[i*2-1]=scan(xa[i],ya[i],yb[i],1);
            sca[i*2]=scan(xb[i],ya[i],yb[i],-1);
        }lh=n*2;
        sort(lsh+1,lsh+lh+1);
        lh=unique(lsh+1,lsh+lh+1)-lsh-1;
        xds.build(1,1,lh);int sum;
        sort(sca+1,sca+2*n+1);
        fo(i,1,n*2){
            sca[i].yl=lower_bound(lsh+1,lsh+lh+1,sca[i].yl)-lsh;
            sca[i].yr=lower_bound(lsh+1,lsh+lh+1,sca[i].yr)-lsh-1;
            //cout<<sca[i].yl<<" "<<sca[i].yr<<endl;
            xds.ins(1,1,lh,sca[i].yl,sca[i].yr,sca[i].tp);
            if(i!=n*2){
                sum=(xds.t1[1]>=n-1?xds.s1[1]:0)+(xds.t2[1]>=n-1?xds.s2[1]:0);
                ans+=(sca[i+1].x-sca[i].x)*sum;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3e5+5;
int T,p,q,n,ans;
int xa[N],xb[N],ya[N],yb[N];
int pxa[N],pxb[N],pya[N],pyb[N];
void maxx(int x,int y,int z){
    pxa[z]=max(pxa[x],xa[y]);
    pxb[z]=min(pxb[x],xb[y]);
    pya[z]=max(pya[x],ya[y]);
    pyb[z]=min(pyb[x],yb[y]);
}
signed main(){
    freopen("carpet.in","r",stdin);
    freopen("carpet.out","w",stdout);
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld",&p,&q,&n);ans=0;
        fo(i,1,n){
            scanf("%lld%lld%lld%lld",&xa[i],&ya[i],&xb[i],&yb[i]);
        }
        memset(pxa,0,sizeof(pxa));
        memset(pxb,0x3f,sizeof(pxb));
        memset(pya,0,sizeof(pya));
        memset(pyb,0x3f,sizeof(pyb));
        fo(i,1,n)maxx(i-1,i,i);
        fu(i,n,1){
            pxa[n+1]=max(pxa[i-1],pxa[n+2]);
            pxb[n+1]=min(pxb[i-1],pxb[n+2]);
            pya[n+1]=max(pya[i-1],pya[n+2]);
            pyb[n+1]=min(pyb[i-1],pyb[n+2]);
            int x=pxb[n+1]-pxa[n+1];if(x<0)x=0;
            int y=pyb[n+1]-pya[n+1];if(y<0)y=0;
            ans+=x*y;
            maxx(n+1,i,n+1);
            x=pxb[n+1]-pxa[n+1];if(x<0)x=0;
            y=pyb[n+1]-pya[n+1];if(y<0)y=0;
            if(i!=1)ans-=x*y;
            maxx(n+2,i,n+2);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3005;
const int bas=131;
int a,b,n,ans;
char s[N];
ull hs[N],ba[N],cf[N][N];
int ys[N][N],pd[N][N];
ull get(int l,int r){return hs[r]-hs[l-1]*ba[r-l+1];}
signed main(){
    freopen("melody.in","r",stdin);
    freopen("melody.out","w",stdout);
    // cout<<(sizeof(cf)*3>>20)<<endl;
    scanf("%d%d",&a,&b);
    scanf("%s",s+1);n=strlen(s+1);
    ba[0]=1;fo(i,1,n){
        ba[i]=ba[i-1]*bas;
        hs[i]=hs[i-1]*bas+s[i]-'a';
    }
    fo(i,1,n){
        cf[i][1]=1;
        fo(j,2,n/i)cf[i][j]=cf[i][j-1]*ba[i]+1;
    }
    fo(i,1,n){
        int now=i;
        fo(j,2,sqrt(now))
            if(now%j==0){
                ys[i][++ys[i][0]]=j;
                while(now%j==0)now/=j;
            }
        if(now!=1)ys[i][++ys[i][0]]=now;
    }
    fo(i,1,n){
        fo(j,1,i){
            ull ha=get(j,i);
            int len=i-j+1;
            if(!ys[len][0]){pd[j][i]=1;continue;}
            pd[j][i]=1;
            fo(k,1,ys[len][0]){
                if(get(j,len/ys[len][k]+j-1)*cf[len/ys[len][k]][ys[len][k]]==ha){
                    ans=max(ans,max(len/ys[len][k]*a+ys[len][k]*b,len/ys[len][k]/pd[j][len/ys[len][k]+j-1]*a+ys[len][k]*pd[j][len/ys[len][k]+j-1]*b));
                    pd[j][i]=ys[len][k]*pd[j][len/ys[len][k]+j-1];break;
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=50005;
const int M=2e5+5;
int n,m,ans;
int r[N];
int to[M*2],nxt[M*2],head[N],rp;
int du[N];
void add_edg(int x,int y){
    to[++rp]=y;
    nxt[rp]=head[x];
    head[x]=rp;
}
int fa[N],siz[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
vector<int> vec[N];
bool com(int x,int y){return x>y;}
void spj(){
    fo(i,1,n)vec[find(i)].push_back(r[i]);
    fo(i,1,n)if(find(i)==i){
        if(vec[i].size()<4)continue;
        sort(vec[i].begin(),vec[i].end(),com);
        ans=max(ans,(vec[i][0]+1)*(vec[i][1]+1)+vec[i][2]*vec[i][3]);
    }
    printf("%d",ans);
}
queue<int> q;
bool vis[N];
signed main(){
    freopen("station.in","r",stdin);
    freopen("station.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,n)scanf("%d",&r[i]);
    fo(i,1,n)fa[i]=i,siz[i]=1;
    fo(i,1,m){
        int x,y;scanf("%d%d",&x,&y);
        add_edg(x,y);add_edg(y,x);
        du[x]++;du[y]++;
        int fx=find(x),fy=find(y);
        if(fx==fy)continue;
        if(x<y)siz[fx]+=siz[fy],fa[fy]=fx;
        else siz[fy]+=siz[fx],fa[fx]=fy;
    }
    bool fl=true;
    fo(i,1,n)if(du[i]!=siz[find(i)]-1)fl=false;
    if(fl){spj();return 0;}
    int sb=clock();
    fo(i,1,n){
        for(int j=head[i];j;j=nxt[j])q.push(to[j]),vis[to[j]]=true;
        while(!q.empty()){
            int x=q.front(),mx=0,mi=0;q.pop();
            for(int j=head[x];j;j=nxt[j]){
                if(!vis[to[j]])continue;
                if(r[to[j]]>mx)mi=mx,mx=r[to[j]];
                else if(r[to[j]]>mi)mi=r[to[j]];
            }
            if(mx&&mi)ans=max(ans,(r[i]+1)*(r[x]+1)+mx*mi);
            if(clock()-sb>=5600000){printf("%d",ans);return 0;}
        }
        for(int j=head[i];j;j=nxt[j])vis[to[j]]=false;
    }
    printf("%d",ans);
    return 0;
}