B. Playing in a Casino

Galaxy Luck, a well-known casino in the entire solar system, introduces a new card game. In this game, there is a deck that consists of 𝑛 cards. Each card has 𝑚 numbers written on it. Each of the 𝑛 players receives exactly one card from the deck. Then all players play with each other in pairs, and each pair of players plays exactly once. Thus, if there are, for example, four players in total, then six games are played: the first against the second, the first against the third, the first against the fourth, the second against the third, the second against the fourth and the third against the fourth.

time limit per test: 2 seconds

memory limit per test: 256 megabytes

Galaxy Luck, a well-known casino in the entire solar system, introduces a new card game.

In this game, there is a deck that consists of n cards. Each card has m numbers written on it. Each of the n players receives exactly one card from the deck.

Then all players play with each other in pairs, and each pair of players plays exactly once. Thus, if there are, for example, four players in total, then six games are played: the first against the second, the first against the third, the first against the fourth, the second against the third, the second against the fourth and the third against the fourth.

Each of these games determines the winner in some way, but the rules are quite complicated, so we will not describe them here. All that matters is how many chips are paid out to the winner. Let the first player's card have the numbers a₁,a₂,…,a_m, and the second player's card — b₁,b₂,…,b_m. Then the winner of the game gets |a₁−b₁|+|a₂−b₂|+⋯+|a_m−b_m| chips from the total pot, where |x| denotes the absolute value of x.

To determine the size of the total pot, it is necessary to calculate the winners' total winnings for all games. Since there can be many cards in a deck and many players, you have been assigned to write a program that does all the necessary calculations.

Input

Each test consists of several test cases. The first line contains one integer t (1≤t≤1000) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n and m (1≤n⋅m≤3⋅10⁵) — the number of cards in the deck and the count of numbers on the one card.

Each of the following n lines of the test case set contains m integers c_i,j (1≤c_i,j≤10⁶) — a description of the i-th card.

It is guaranteed that the total n⋅m in all tests does not exceed 3⋅10⁵.

Output

For each test case, print one number — the total amount of winnings from all games.

Example

Input

Output

50
0
31

Note

Consider the first test case.

In the game between the first and second player, the winner receives |1−7|+|4−9|+|2−2|+|8−1|+|5−4|=19 chips.

In the game between the first and third player, the winner receives |1−3|+|4−8|+|2−5|+|8−3|+|5−1|=18 in chips.

In the game between the second and third player, the winner receives |7−3|+|9−8|+|2−5|+|1−3|+|4−1|=13 chips.

The total is 19+18+13=50 chips.

Understanding the Problem Statement

- We have n players, each with a card containing m numbers.
- Each pair of players plays against each other, and the winner gets a payout equal to the sum of absolute differences of corresponding numbers on the cards.
- Our goal is to compute the total winnings across all pairs of games.

Breaking Down the Approach

1. Rearranging Data by Column

- Instead of comparing every pair of n cards directly (which would be inefficient), we process each column (position on the card) separately.
- This means, for each column j, we gather all n numbers into a list v[j].

2. Sorting for Efficient Computation

- Sorting helps because for a sorted list [x1, x2, ..., xn], the total sum of absolute differences is computed efficiently using a prefix sum approach.

3. Mathematical Trick

Consider a sorted array v[j] = [x1, x2, ..., xn]:
- The total sum of absolute differences for all pairs is calculated using:

    ∑(v[j][i-1] × (i-1) - prefix sum of previous values)

- This works because:
- A number x_k contributes positively when it is a larger number in pairs.
- A number x_k contributes negatively when it is a smaller number in pairs.

4. Implementation Details

- The input is read into a 2D vector a[n][m].
- A new array v[m] is created where v[j] contains all n numbers from column j.
- Each v[j] is sorted.
- Using prefix sums, the total absolute differences are computed efficiently in O(n log n) for each column.

Time Complexity Analysis

- Sorting each column takes O(n log n).
- Computing the sum of absolute differences takes O(n) per column.
- Since there are m columns, the total complexity is O(m * n log n).
- Given the constraints (n * m ≤ 3 * 10⁵), this is optimal.

Verifying the Example

We extract the columns:

Column 1: [1, 7, 3]
Column 2: [4, 9, 8]
Column 3: [2, 2, 5]
Column 4: [8, 1, 3]
Column 5: [5, 4, 1]

Sorting and applying the formula, the sum of absolute differences is computed correctly as 50.

void solve()
{

  int n, m;
  cin >> n >> m;

  vector<vi> a(n, vi(m));

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> a[i][j];
    }
  }

  vector<vi> v(m);

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      v[j].push_back(a[i][j]);
    }
  }

  int res = 0;
  for (int i = 0; i < m; i++)
  {
    sort(v[i].begin(), v[i].end());
    vector<int> pre(n + 1);
    for (int j = 1; j <= n; j++)
    {
      res += v[i][j - 1] * (j - 1) - pre[j - 1];
      pre[j] += pre[j - 1] + v[i][j - 1];
    }
  }

  cout << res << endl;
}


#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define F first
#define S second
#define pb push_back
#define si set<int>
#define vi vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vpp vector<pair<int, pii>>
#define mii map<int, int>
#define mpi map<pii, int>
#define spi set<pii>
#define endl "\n"
#define sz(x) ((int)x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue<int>
#define que_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define print(a)      \
  for (auto x : a)    \
    cout << x << " "; \
  cout << endl
#define print1(a)  \
  for (auto x : a) \
  cout << x.F << " " << x.S << endl
#define print2(a, x, y)       \
  for (int i = x; i < y; i++) \
    cout << a[i] << " ";      \
  cout << endl
#define scanit(a, n)                           \
  for (ll indexaa = 0; indexaa < n; indexaa++) \
    cin >> a[indexaa];

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1)
      x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args)
{
  const char *comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}

const int N = 200005;

void solve()
{

  int n, m;
  cin >> n >> m;

  vector<vi> a(n, vi(m));

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> a[i][j];
    }
  }

  vector<vi> v(m);

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      v[j].push_back(a[i][j]);
    }
  }

  int res = 0;
  for (int i = 0; i < m; i++)
  {
    sort(v[i].begin(), v[i].end());
    vector<int> pre(n + 1);
    for (int j = 1; j <= n; j++)
    {
      res += v[i][j - 1] * (j - 1) - pre[j - 1];
      pre[j] += pre[j - 1] + v[i][j - 1];
    }
  }

  cout << res << endl;
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  clock_t z = clock();

  int t = 1;
  cin >> t;
  while (t--)
    solve();

  return 0;
}

TagsCodeforces Round 861 (Div. 2)B. Playing in a CasinoCodeforces SolutionC++Codeforces

Raunit Verma

Technical Writer at CodingKaro

Share this on