1. Abridged Problem Statement
You have 3N integers. Partition them into three sequences A, B, C of length N each (each original number used exactly once) to maximize
   S = Σ_{i=1..N} (A_i – B_i) * C_i.
You may reorder A, B, C arbitrarily after choosing their elements. Given T test cases with the same N, output the maximum S for each.

2. Detailed Editorial

Overview
1.  Sort all 3N numbers ascending; call them X[0..3N–1].
2.  It is always optimal to take the N smallest values as B (since they enter with a minus sign). Call these B[0..N–1], already sorted.
3.  Let AC = the remaining 2N numbers, sorted ascending. We must split AC into two size-N subsets: A and C.  After deciding which go to A and which to C, we sort A ascending and C ascending, then pair them in index order to form the sum
      Σ_{i=0..N–1} (A[i] – B[i]) * C[i].

Brute-forcing all ways to choose N out of 2N for A is O(C(2N,N)), too big for N up to 25.
Instead we use a 2^N-state DP that "slides" a window of width N along the sorted AC array and maintains which slots in the current window are already used by C.  A clever bitmask-shift trick reuses states across windows so we only ever need 2^N DP entries.

Key DP idea ("mask rolling")
- Let v = AC sorted ascending of size 2N.
- We will process v in decreasing order (from largest to smallest).  At each of 2N steps we either assign the current element to A or to C.
- We maintain a bitmask mask of length N.  The ones in mask mark which "C-slots" in the current sliding window have already been filled.  The zeros are still free to take a new C.
- The count of bits set in mask is cnt = how many C's we have already chosen so far.  Equivalently we have N–cnt A's chosen (out of the N slots) to pair with the C's.  Each time we move to the next element (one position down in AC), we "shift" the window by one to reflect that now one new potential slot enters at the top.  We find that the only sensible place to put the new A is in the newest (top) slot, while the new C can go into any zero-bit position i before the first one-bit in next_mask.
- We precompute popcnt[mask] for all masks.  We keep dp[mask] = max total so far when our current mask is mask.
- Transition from mask:
    1. Compute cnt = popcnt[mask].
    2. Shift mask left by 1 bit, drop the top; then flip exactly one zero-bit in the new mask to one (this "recycles" the oldest A-slot back into play).
    3. Call that intermediate state next_mask.
    4. For each i from 0..N–1 such that next_mask has bit i = 0 (stop at the first 1-bit — the inner loop uses break), we can choose to put current element v[j] into C at slot i.  That slot i corresponds to pairing with A at slot top_zero (the one we fresh-allocated).
    5. The contribution of pairing that A (call it A_val) with this C (call it C_val) is (A_val – B[cnt]) * C_val.
    6. We set dp[next_mask | (1<<i)] = max(dp[next_mask | (1<<i)], dp[mask] + (A_val–B[cnt]) * C_val).

After processing all 2N elements, the answer is in dp[(1<<N)–1] (all bits = 1).

Complexities
- States: 2^N (N ≤ 25 ⇒ at most 2^25 ≈ 33 million states).
- Each state does O(N) work. In C++ with bit-operations this runs in ~1–1.5 s for N=25.

3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> vals;

void read() {
    vals.resize(3 * n);
    cin >> vals;
}

int dp[1 << 25];
int8_t popcnt[1 << 25];

void precompute() {
    popcnt[0] = 0;
    for(int mask = 1; mask < (1 << 25); mask++) {
        popcnt[mask] = popcnt[mask >> 1] + (mask & 1);
    }
}

void solve() {
    // Sort the 3N values. It is always optimal to assign the smallest N values
    // to B, leaving the upper 2N values (call them AC) to be split between A
    // and C. We process A/C with a sliding-window bitmask DP: the mask records
    // which of the most recent AC positions have been chosen as C, and popcnt
    // of the mask is how many A/C pairs have been placed. For each mask we form
    // next_mask by shifting left (advancing the window) and inserting the next
    // A at the topmost free position; top_zero tracks that position. Each free
    // bit i in next_mask is a candidate slot for the matching C, and the
    // contribution of pairing the cnt-th largest A with that C, against the
    // cnt-th smallest B, is (A - B) * C. Shifting the window keeps each C close
    // to its A, which is what reduces the naive O*(4^n) to O*(2^n).

    vector<pair<int, int>> v;
    for(int i = 0; i < 3 * n; i++) {
        v.emplace_back(vals[i], i);
    }

    sort(v.begin(), v.end());

    vector<pair<int, int>> B, AC;
    B.insert(B.end(), v.begin(), v.begin() + n);
    AC.insert(AC.end(), v.begin() + n, v.end());

    memset(dp, 0, (1 << n) * sizeof(int));
    int top_zero = n;
    for(int mask = 0; mask < (1 << n); mask++) {
        int cnt = popcnt[mask];
        int next_mask = mask << 1;
        if((next_mask >> top_zero) & 1) {
            top_zero--;
        }

        next_mask |= (1 << top_zero);
        next_mask &= (1 << n) - 1;

        for(int i = 0; i < n; i++) {
            if((next_mask >> i) & 1) {
                break;
            }

            int Bj = B[cnt].first;
            int Aj = AC[n - cnt + top_zero - 1].first;
            int Cj = AC[n - cnt + i - 1].first;

            dp[next_mask | (1 << i)] =
                max(dp[next_mask | (1 << i)], dp[mask] + (Aj - Bj) * Cj);
        }
    }

    cout << dp[(1 << n) - 1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    int T = 1;
    cin >> T >> n;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python Solution

```python
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
    T, n = map(int, input().split())
    FULL = (1 << n) - 1

    # Precompute popcounts for 0..2^n-1
    popcnt = [0] * (1<<n)
    for m in range(1, 1<<n):
        popcnt[m] = popcnt[m>>1] + (m & 1)

    for _ in range(T):
        X = list(map(int, input().split()))
        X.sort()
        # Select B = N smallest
        B = X[:n]
        # The remaining 2N values
        AC = X[n:]

        # dp[mask] = best sum so far with this mask of chosen C-slots
        dp = [0] * (1<<n)

        # 'top_zero' is the index of the fresh slot to recycle each step
        top_zero = n

        # Process masks in ascending order => implicitly from largest AC to smallest
        for mask in range(1<<n):
            cnt = popcnt[mask]       # how many Cs chosen so far
            # Shift window
            next_mask = (mask << 1) & FULL

            # If the bit we dropped was zero, update top_zero
            if ((mask >> (n-1)) & 1) == 0:
                top_zero -= 1
            # Mark the recycled slot as occupied (will be used by an A)
            next_mask |= (1 << top_zero)

            # Try putting the new AC element into any free C-slot
            # The new element in AC that we are placing is at index:
            #    j = n - cnt + *something* - 1, but in mask ordering we simply
            #    recompute Aj,Cj the same way as the C++ logic.
            for i in range(n):
                if (next_mask >> i) & 1:
                    continue
                # B[cnt] is the next B
                Bj = B[cnt]
                # A is from the recycled slot (complex index arithmetic)
                Aj = AC[n - cnt + top_zero - 1]
                # C is from slot i
                Cj = AC[n - cnt + i - 1]
                newmask = next_mask | (1 << i)
                gain = (Aj - Bj) * Cj
                if dp[mask] + gain > dp[newmask]:
                    dp[newmask] = dp[mask] + gain

        # answer in full mask
        print(dp[FULL])

if __name__ == "__main__":
    main()
```

5. Compressed Editorial
- Sort 3N numbers; take N smallest as B.
- Let AC be the other 2N sorted numbers. We must pick N of AC as A and N as C, then pair sorted A[i] with sorted C[i] to maximize Σ(A[i]–B[i])·C[i].
- Brute forcing C(2N,N) is too big. Instead use a 2^N-state DP over a rolling window of width N on AC: a bitmask tracks which "C-slots" are filled, shifting and "recycling" one slot per step to represent the next A.
- Transition in O(N) per mask (inner loop breaks at the first occupied bit), total O(N·2^N). The answer is dp[(1<<N)–1].
