1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Maximum modulo equality
Contest: Codeforces Round 991 (Div. 3)
Difficulty rating: 1700
Tags: data structures, divide and conquer, math, number theory

You are given an array $$$a$$$ of length $$$n$$$ and $$$q$$$ queries $$$l$$$, $$$r$$$.

For each query, find the maximum possible $$$m$$$, such that all elements $$$a_l$$$, $$$a_{l+1}$$$, ..., $$$a_r$$$ are equal modulo $$$m$$$. In other words, $$$a_l \bmod m = a_{l+1} \bmod m = \dots = a_r \bmod m$$$, where $$$a \bmod b$$$ — is the remainder of division $$$a$$$ by $$$b$$$. In particular, when $$$m$$$ can be infinite, print $$$0$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$) — the length of the array and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

In the following $$$q$$$ lines of each test case, two integers $$$l$$$, $$$r$$$ are provided ($$$1 \le l \le r \le n$$$) — the range of the query.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$, and the sum of $$$q$$$ does not exceed $$$2\cdot 10^5$$$.

Output format:
For each query, output the maximum value $$$m$$$ described in the statement.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first query of the first sample, $$$6 \bmod 3 = 3 \bmod 3 = 0$$$. It can be shown that for greater $$$m$$$, the required condition will not be fulfilled.

In the third query of the first sample, $$$14 \bmod 4 = 2 \bmod 4 = 6 \bmod 4 = 2$$$. It can be shown that for greater $$$m$$$, the required condition will not be fulfilled.

Example input:
3
5 5
5 14 2 6 3
4 5
1 4
2 4
3 5
1 1
1 1
7
1 1
3 2
1 7 8
2 3
1 2

Example output:
3 1 4 1 0 
0 
1 6

Editorial:
Let's look at two arbitrary integers $$$x$$$ and $$$y$$$. Now we want to find the maximum $$$m$$$, which satisfies $$$x\bmod m = y\bmod m$$$. We know that $$$x\bmod m = y\bmod m$$$, then $$$|x - y|\bmod m = 0$$$, because they have the same remainder by $$$m$$$. That means that any $$$m$$$ which is a divisor of $$$|x - y|$$$ will satisfy the required condition.
Now let's generalize the idea we've obtained to the segment: $$$a_l\bmod m = a_{l+1}\bmod m = \dots = a_r\bmod m$$$ means that $$$a_l\bmod m = a_{l+1}\bmod m$$$, and $$$a_{l+1}\bmod m = a_{l+2}\bmod m$$$, and ..., and $$$a_{r-1}\bmod m = a_r\bmod m$$$. So, $$$m$$$ must be a divisor of $$$|a_l - a_{l+1}|$$$, $$$|a_{l+1} - a_{l+2}|$$$, ..., $$$|a_{r-1} - a_r|$$$ at the same time. That means that $$$m$$$ should be GCD($$$|a_l - a_{l+1}|$$$, $$$|a_{l+1} - a_{l+2}|$$$, ..., $$$|a_{r-1} - a_r|$$$), where GCD is the greatest common divisor. $$$m = 0$$$, when all the elements on the segment [$$$l; r$$$] are equal.
Let's build an array consisting of differences of adjacent elements; now we can use sparse table to find GCD on the segments efficiently.
Tree Destruction
Contest: Codeforces Round 991 (Div. 3)
Difficulty rating: 1900
Tags: dfs and similar, dp, trees

Given a tree$$$^{\text{∗}}$$$ with $$$n$$$ vertices. You can choose two vertices $$$a$$$ and $$$b$$$ once and remove all vertices on the path from $$$a$$$ to $$$b$$$, including the vertices themselves. If you choose $$$a=b$$$, only one vertex will be removed.

Your task is to find the maximum number of connected components$$$^{\text{†}}$$$ that can be formed after removing the path from the tree.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the size of the tree.

The next $$$n-1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — the vertices connected by an edge. It is guaranteed that the edges form a tree.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output one integer — the maximum number of connected components that can be achieved using the described operation.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6
2
1 2
5
1 2
2 3
3 4
3 5
4
1 2
2 3
3 4
5
2 1
3 1
4 1
5 4
6
2 1
3 1
4 1
5 3
6 3
6
2 1
3 2
4 2
5 3
6 4

Example output:
1
3
2
3
4
3

Editorial:
Let's choose some vertices $$$a$$$ and $$$b$$$, between which there are $$$k$$$ edges. Then, when removing this path, the tree will split into $$$s - 2 \cdot k$$$, where $$$s$$$ is the sum of the degrees of the vertices on the path (this is exactly how many edges are connected to the chosen path).
Let's suspend the tree from vertex $$$1$$$, and for each vertex $$$v$$$ of the given tree, we will calculate two values: $$$\text{dp[v].x}$$$ — the best answer if the path starts at vertex $$$v$$$ and ends in its subtree, and $$$\text{dp[v].y}$$$ — the best answer if the path passes through vertex $$$v$$$ from one of its children to another. The recalculations of the dynamic programming will be similar to those used in finding the diameter of the tree using dynamic programming.
The answer will be the largest value among all $$$\text{dp[v].x}$$$ and $$$\text{dp[v].y}$$$.
Turtle and Good Strings
Contest: Codeforces Round 968 (Div. 2)
Difficulty rating: 800
Tags: greedy, strings

Turtle thinks a string $$$s$$$ is a good string if there exists a sequence of strings $$$t_1, t_2, \ldots, t_k$$$ ($$$k$$$ is an arbitrary integer) such that:

- $$$k \ge 2$$$.
- $$$s = t_1 + t_2 + \ldots + t_k$$$, where $$$+$$$ represents the concatenation operation. For example, $$$\texttt{abc} = \texttt{a} + \texttt{bc}$$$.
- For all $$$1 \le i < j \le k$$$, the first character of $$$t_i$$$ isn't equal to the last character of $$$t_j$$$.

Turtle is given a string $$$s$$$ consisting of lowercase Latin letters. Please tell him whether the string $$$s$$$ is a good string!

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the string.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters.

Output format:
For each test case, output "YES" if the string $$$s$$$ is a good string, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the sequence of strings $$$\texttt{a}, \texttt{a}$$$ satisfies the condition $$$s = t_1 + t_2 + \ldots + t_k$$$, but the first character of $$$t_1$$$ is equal to the last character of $$$t_2$$$. It can be seen that there doesn't exist any sequence of strings which satisfies all of the conditions, so the answer is "NO".

In the third test case, the sequence of strings $$$\texttt{ab}, \texttt{cb}$$$ satisfies all of the conditions.

In the fourth test case, the sequence of strings $$$\texttt{abca}, \texttt{bcab}, \texttt{cabc}$$$ satisfies all of the conditions.

Example input:
4
2
aa
3
aba
4
abcb
12
abcabcabcabc

Example output:
No
nO
Yes
YES

Editorial:
A necessary condition for $$$s$$$ to be good is that $$$s_1 \ne s_n$$$. For a string $$$s$$$ where $$$s_1 \ne s_n$$$, let $$$t_1$$$ be a string composed of just the single character $$$s_1$$$, and let $$$t_2$$$ be a string composed of the $$$n - 1$$$ characters from $$$s_2$$$ to $$$s_n$$$. In this way, the condition is satisfied.
Therefore, if $$$s_1 \ne s_n$$$, the answer is "Yes"; otherwise, the answer is "No".
Time complexity: $$$O(n)$$$ per test case.
Kevin and Combination Lock
Contest: Codeforces Global Round 28
Difficulty rating: 800
Tags: brute force, greedy, implementation, math, number theory

Kevin is trapped in Lakeside Village by Grace. At the exit of the village, there is a combination lock that can only be unlocked if Kevin solves it.

The combination lock starts with an integer $$$ x $$$. Kevin can perform one of the following two operations zero or more times:

1. If $$$ x \neq 33 $$$, he can select two consecutive digits $$$ 3 $$$ from $$$ x $$$ and remove them simultaneously. For example, if $$$ x = 13\,323 $$$, he can remove the second and third $$$ 3 $$$, changing $$$ x $$$ to $$$ 123 $$$.
2. If $$$ x \geq 33 $$$, he can change $$$ x $$$ to $$$ x - 33 $$$. For example, if $$$ x = 99 $$$, he can choose this operation to change $$$ x $$$ to $$$ 99 - 33 = 66 $$$.

When the value of $$$ x $$$ on the combination lock becomes $$$ 0 $$$, Kevin can unlock the lock and escape from Lakeside Village. Please determine whether it is possible for Kevin to unlock the combination lock and escape.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$).

The only line of each test case contains a positive integer $$$x$$$ ($$$1\leq x\leq 10^9$$$).

Output format:
For each test case, output "YES" or "NO" (without quotes) in one line, representing whether Kevin can unlock the combination lock and escape. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test case, $$$165\xrightarrow{-33}132\xrightarrow{-33}99\xrightarrow{-33}66\xrightarrow{-33}33\xrightarrow{-33}0$$$.

For the second test case, $$$6369\xrightarrow{-33}6{\color{red}{33}}6\xrightarrow{\text{remove "33"}}66\xrightarrow{-33}33\xrightarrow{-33}0$$$.

For the third test case, it can be proven that, regardless of the operations performed, $$$666$$$ cannot be transformed into $$$0$$$.

Example input:
5
165
6369
666
114514
133333332

Example output:
YES
YES
NO
NO
YES

Editorial:
Hint #1: How much does the number decrease when we remove two consecutive $$$3$$$s?
When we transform $$$\overline{x33y}$$$ into $$$\overline{xy}$$$ (where $$$x$$$ and $$$y$$$ are decimal numbers), the actual value changes from $$$10^{p+2} \cdot x + 33 \cdot 10^p + y$$$ to $$$10^p \cdot x + y$$$. The decrease is $$$99 \cdot 10^p \cdot x + 33 \cdot 10^p$$$. It is easy to see that $$$33 \mid (99 \cdot 10^p \cdot x + 33 \cdot 10^p)$$$. Therefore, we can replace the operation of "removing two consecutive $$$3$$$s" with a series of "$$$-33$$$" operations.
Hence, we only need to determine whether $$$x$$$ can be reduced to $$$0$$$ using a series of $$$-33$$$ operations, which is equivalent to checking whether $$$x \bmod 33$$$ equals zero.
Kevin and Permutation
Contest: Codeforces Global Round 28
Difficulty rating: 900
Tags: constructive algorithms, greedy

Kevin is a master of permutation-related problems. You are taking a walk with Kevin in Darkwoods, and during your leisure time, he wants to ask you the following question.

Given two positive integers $$$ n $$$ and $$$ k $$$, construct a permutation$$$^{\text{∗}}$$$ $$$ p $$$ of length $$$ n $$$ to minimize the sum of the minimum values of all subarrays$$$^{\text{†}}$$$ of length $$$ k $$$. Formally, you need to minimize

$$$$$$ \sum_{i=1}^{n-k+1}\left( \min_{j=i}^{i+k-1} p_j\right). $$$$$$

Input format:
Each test consists of multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$).

The only line of each test case contains two integers $$$ n $$$ and $$$ k $$$ ($$$ 1\le k\le n\le 10^5 $$$).

It is guaranteed that the sum of $$$ n $$$ over all test cases doesn't exceed $$$ 10^5 $$$.

Output format:
For each test case, output $$$ n $$$ integers on a single line — the permutation $$$ p $$$ you constructed.

If there are multiple answers, you can print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, with $$$ k=2 $$$, consider all subarrays of length $$$ 2 $$$: the minimum value of $$$ p_1,p_2 $$$ is $$$ 1 $$$, the minimum value of $$$ p_2,p_3 $$$ is $$$ 1 $$$, and the minimum value of $$$ p_3,p_4 $$$ is $$$ 2 $$$. The sum $$$ 1+1+2=4 $$$ is the smallest among all possible permutations.

In the second test case, all subarrays of length $$$ 1 $$$ have minimum values of $$$ 5, 2, 1, 6, 4, 3 $$$, and the sum $$$ 5+2+1+6+4+3=21 $$$ is proven to be the smallest.

Example input:
3
4 2
6 1
8 3

Example output:
3 1 2 4
5 2 1 6 4 3
4 6 2 8 3 1 5 7

Editorial:
Hint #1: If the permutation is sufficiently long, what is the maximum number of length $$$k$$$ subintervals where the minimum value is $$$1$$$?
In the entire permutation, at most $$$k$$$ subintervals can contain $$$1$$$. Similarly, at most $$$k$$$ subintervals can contain $$$2, 3, \dots$$$. To maximize the number of subintervals where the minimum value is as small as possible, we use the following construction:
$$$$$$ p_k=1,p_{2k}=2,\dots,p_{\lfloor{\frac{n}{k}}\rfloor\cdot k}=\left\lfloor\frac{n}{k}\right\rfloor $$$$$$
For the remaining positions, we can fill them arbitrarily with all values from $$$\lfloor \frac{n}{k} \rfloor + 1$$$ to $$$n$$$. It is easy to prove that this construction minimizes the answer.
Skibidus and Amog'u
Contest: Codeforces Round 1003 (Div. 4)
Difficulty rating: 800
Tags: brute force, constructive algorithms, greedy, implementation, strings

Skibidus lands on a foreign planet, where the local Amog tribe speaks the Amog'u language. In Amog'u, there are two forms of nouns, which are singular and plural.

Given that the root of the noun is transcribed as $$$S$$$, the two forms are transcribed as:

- Singular: $$$S$$$ $$$+$$$ "us"
- Plural: $$$S$$$ $$$+$$$ "i"

Here, $$$+$$$ denotes string concatenation. For example, abc $$$+$$$ def $$$=$$$ abcdef.

For example, when $$$S$$$ is transcribed as "amog", then the singular form is transcribed as "amogus", and the plural form is transcribed as "amogi". Do note that Amog'u nouns can have an empty root — in specific, "us" is the singular form of "i" (which, on an unrelated note, means "imposter" and "imposters" respectively).

Given a transcribed Amog'u noun in singular form, please convert it to the transcription of the corresponding plural noun.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The only line of each test case contains a string $$$W$$$, which is a transcribed Amog'u noun in singular form. It is guaranteed that $$$W$$$ consists of only lowercase English letters, has a length of at most $$$10$$$, and ends with "us".

Output format:
For each test case, output the transcription of the corresponding plural noun on a separate line.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
9
us
sus
fungus
cactus
sussus
amogus
chungus
ntarsus
skibidus

Example output:
i
si
fungi
cacti
sussi
amogi
chungi
ntarsi
skibidi

Editorial:
Skibidus and Ohio
Contest: Codeforces Round 1003 (Div. 4)
Difficulty rating: 800
Tags: strings

Skibidus is given a string $$$s$$$ that consists of lowercase Latin letters. If $$$s$$$ contains more than $$$1$$$ letter, he can:

- Choose an index $$$i$$$ ($$$1 \leq i \leq |s| - 1$$$, $$$|s|$$$ denotes the current length of $$$s$$$) such that $$$s_i = s_{i+1}$$$. Replace $$$s_i$$$ with any lowercase Latin letter of his choice. Remove $$$s_{i+1}$$$ from the string.

Skibidus must determine the minimum possible length he can achieve through any number of operations.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The only line of each test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 100$$$). It is guaranteed $$$s$$$ only contains lowercase Latin letters.

Output format:
For each test case, output an integer on the new line, the minimum achievable length of $$$s$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Skibidus can:

- Perform an operation on $$$i = 2$$$. He replaces $$$s_2$$$ with b and removes $$$s_3$$$ from the string. Then, $$$s$$$ becomes bb.
- Perform an operation on $$$i = 1$$$. He replaces $$$s_1$$$ with b and removes $$$s_2$$$ from the string. Then, $$$s$$$ becomes b.
- Because $$$s$$$ only contains $$$1$$$ letter, Skibidus cannot perform any more operations.

Therefore, the answer is $$$1$$$ for the first test case.

In the second test case, he cannot perform an operation on any index. Therefore, the answer is still the length of the initial string, $$$8$$$.

Example input:
4
baa
skibidus
cc
ohio

Example output:
1
8
1
4

Editorial:
Skibidus and Fanum Tax (easy version)
Contest: Codeforces Round 1003 (Div. 4)
Difficulty rating: 1100
Tags: binary search, dp, greedy

This is the easy version of the problem. In this version, $$$m = 1$$$.

Skibidus has obtained two arrays $$$a$$$ and $$$b$$$, containing $$$n$$$ and $$$m$$$ elements respectively. For each integer $$$i$$$ from $$$1$$$ to $$$n$$$, he is allowed to perform the operation at most once:

- Choose an integer $$$j$$$ such that $$$1 \leq j \leq m$$$. Set $$$a_i := b_j - a_i$$$. Note that $$$a_i$$$ may become non-positive as a result of this operation.

Skibidus needs your help determining whether he can sort $$$a$$$ in non-decreasing order$$$^{\text{∗}}$$$ by performing the above operation some number of times.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$\textbf{m = 1}$$$).

The following line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The following line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, if it is possible to sort $$$a$$$ in non-decreasing order, print "YES" on a new line. Otherwise, print "NO" on a new line.

You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" will also be recognized as positive responses.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$[5]$$$ is already sorted.

In the second test case, it can be shown that it is impossible.

In the third test case, we can set $$$a_3:=b_1-a_3=6-2=4$$$. The sequence $$$[1,4,4,5]$$$ is in nondecreasing order.

In the last case, we can apply operations on each index. The sequence becomes $$$[-1,0,1]$$$, which is in nondecreasing order.

Example input:
5
1 1
5
9
3 1
1 4 3
3
4 1
1 4 2 5
6
4 1
5 4 10 5
4
3 1
9 8 7
8

Example output:
YES
NO
YES
NO
YES

Editorial:
Skibidus and Fanum Tax (hard version)
Contest: Codeforces Round 1003 (Div. 4)
Difficulty rating: 1300
Tags: binary search, greedy

This is the hard version of the problem. In this version, $$$m \leq 2\cdot 10^5$$$.

Skibidus has obtained two arrays $$$a$$$ and $$$b$$$, containing $$$n$$$ and $$$m$$$ elements respectively. For each integer $$$i$$$ from $$$1$$$ to $$$n$$$, he is allowed to perform the operation at most once:

- Choose an integer $$$j$$$ such that $$$1 \leq j \leq m$$$. Set $$$a_i := b_j - a_i$$$. Note that $$$a_i$$$ may become non-positive as a result of this operation.

Skibidus needs your help determining whether he can sort $$$a$$$ in non-decreasing order$$$^{\text{∗}}$$$ by performing the above operation some number of times.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 2\cdot 10^5$$$).

The following line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The following line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, if it is possible to sort $$$a$$$ in non-decreasing order, print "YES" on a new line. Otherwise, print "NO" on a new line.

You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" will also be recognized as positive responses.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$[5]$$$ is already sorted.

In the second test case, it can be shown that it is impossible.

In the third test case, we can set $$$a_2:=b_1-a_2=6-4=2$$$ and $$$a_3:=b_3-a_3=8-6=2$$$. The sequence $$$[2,2,2,5]$$$ is in nondecreasing order.

In the last case, we can apply operations on each index. The sequence becomes $$$[-1,0,1]$$$, which is in nondecreasing order.

Example input:
5
1 3
5
9 1 1000000000
3 2
1 4 3
3 4
4 3
2 4 6 5
6 1 8
5 2
6 4 5 4 5
4 1000
3 1
9 8 7
8

Example output:
YES
NO
YES
NO
YES

Editorial:
Skibidus and Sigma
Contest: Codeforces Round 1003 (Div. 4)
Difficulty rating: 1200
Tags: greedy, sortings

Let's denote the score of an array $$$b$$$ with $$$k$$$ elements as $$$\sum_{i=1}^{k}\left(\sum_{j=1}^ib_j\right)$$$. In other words, let $$$S_i$$$ denote the sum of the first $$$i$$$ elements of $$$b$$$. Then, the score can be denoted as $$$S_1+S_2+\ldots+S_k$$$.

Skibidus is given $$$n$$$ arrays $$$a_1,a_2,\ldots,a_n$$$, each of which contains $$$m$$$ elements. Being the sigma that he is, he would like to concatenate them in any order to form a single array containing $$$n\cdot m$$$ elements. Please find the maximum possible score Skibidus can achieve with his concatenated array!

Formally, among all possible permutations$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$, output the maximum score of $$$a_{p_1} + a_{p_2} + \dots + a_{p_n}$$$, where $$$+$$$ represents concatenation$$$^{\text{†}}$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — the number of arrays and the length of each array.

The $$$i$$$'th of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$1 \leq a_{i,j} \leq 10^6$$$) — the elements of the $$$i$$$'th array.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the maximum score among all possible permutations $$$p$$$ on a new line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, there are two possibilities for $$$p$$$:

- $$$p = [1, 2]$$$. Then, $$$a_{p_1} + a_{p_2} = [4, 4, 6, 1]$$$. Its score is $$$4+(4+4)+(4+4+6)+(4+4+6+1)=41$$$.
- $$$p = [2, 1]$$$. Then, $$$a_{p_1} + a_{p_2} = [6, 1, 4, 4]$$$. Its score is $$$6+(6+1)+(6+1+4)+(6+1+4+4)=39$$$.

The maximum possible score is $$$41$$$.

In the second test case, one optimal arrangement of the final concatenated array is $$$[4,1,2,1,2,2,2,2,3,2,1,2]$$$. We can calculate that the score is $$$162$$$.

Example input:
3
2 2
4 4
6 1
3 4
2 2 2 2
3 2 1 2
4 1 2 1
2 3
3 4 5
1 1 9

Example output:
41
162
72

Editorial: