Permutations Harmony
Contest: Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
Difficulty rating: 2200
Tags: combinatorics, constructive algorithms, greedy, hashing, math

Rayan wants to present a gift to Reyhaneh to win her heart. However, Reyhaneh is particular and will only accept a k-harmonic set of permutations.

We define a k-harmonic set of permutations as a set of $$$k$$$ pairwise distinct permutations $$$p_1, p_2, \ldots, p_k$$$ of size $$$n$$$ such that for every pair of indices $$$i$$$ and $$$j$$$ (where $$$1 \leq i, j \leq n$$$), the following condition holds:

$$$$$$ p_1[i] + p_2[i] + \ldots + p_k[i] = p_1[j] + p_2[j] + \ldots + p_k[j] $$$$$$

Your task is to help Rayan by either providing a valid k-harmonic set of permutations for given values of $$$n$$$ and $$$k$$$ or by determining that such a set does not exist.

We call a sequence of length $$$n$$$ a permutation if it contains every integer from $$$1$$$ to $$$n$$$ exactly once.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$), the number of test cases.

Each test case consists of two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n, k \leq 10^5$$$). The sum of $$$n \cdot k$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, if a k-harmonic set of permutations exists, print YES on the first line. Then, print $$$k$$$ lines, each containing a distinct permutation of the integers from $$$1$$$ to $$$n$$$.

If no such set exists, print NO on the first line.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", and "Yes" will be recognized as a positive response).

If multiple answers are possible, you can output any of them.

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

Note:
In example 1, we have $$$p_1 = [1, 2, 3]$$$, $$$p_2 = [2, 3, 1]$$$, and $$$p_3 = [3, 1, 2]$$$. It's easy to see that $$$p_1[1] + p_2[1] + p_3[1] = p_1[2] + p_2[2] + p_3[2] = p_1[3] + p_2[3] + p_3[3] = 6$$$.

In example 2, we have $$$p_1 = [1, 2, 3, 4]$$$ and $$$p_2 = [4, 3, 2, 1]$$$. It's easy to see that $$$p_1[1] + p_2[1] = p_1[2] + p_2[2] = p_1[3] + p_2[3] = p_1[4] + p_2[4] = 5$$$.

In example 3, as there are five distinct elements in $$$p_1$$$, it's obvious that the answer is "No".

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

Example output:
YES
1 2 3
2 3 1
3 1 2
YES
1 2 3 4
4 3 2 1
NO
YES
1 2 3
3 2 1

Editorial:
1. There are $$$n$$$ positions that must be equal together, and their sum is $$$\frac{n \cdot (n+1) \cdot k}{2}$$$. Hence, each position must be $$$\frac{(n+1) \cdot k}{2}$$$. Additionally, there must be $$$k$$$ distinct permutations, so $$$k \le n!$$$.
2. For even $$$k$$$, we can group $$$n!$$$ permutations into $$$\frac{n!}{2}$$$ double handles, where each group is a solution for $$$k=2$$$. Then, pick $$$\frac{k}{2}$$$ handles. The match of permutation $$$a_1, a_2, \ldots, a_n$$$ is $$$(n+1)-a_1, (n+1)-a_2, \ldots, (n+1)-a_n$$$.
3. For $$$k = 1$$$, $$$n$$$ must be $$$1$$$. Symmetrically, $$$k$$$ cannot be $$$n!-1$$$. Solutions for other odd $$$k$$$ will now be provided.
4. To construct an answer for $$$k = 3$$$ and $$$n = 2x + 1$$$, consider the following derived using a greedy approach: 12345$$$\ldots$$$$$$2x-1$$$$$$2x$$$$$$2x+1$$$$$$x+1$$$$$$2x+1$$$$$$x$$$$$$2x$$$$$$x-1$$$$$$\ldots$$$$$$2$$$$$$x+2$$$$$$1$$$$$$2x+1$$$$$$x$$$$$$2x$$$$$$x-1$$$$$$2x-1$$$$$$\ldots$$$$$$x+2$$$$$$1$$$$$$x+1$$$
5. Now, combine the solution for even $$$k$$$ and the $$$k=3$$$ solution by selecting the $$$3$$$ permutations and $$$\frac{k-3}{2}$$$ other handles.