Description

Xiao Yu'er is a math genius. One night he studied a Penney-ante game related to strings. The rules are as follows:

1. There are two players. At the beginning, each chooses a string of the same length.
2. A character generator keeps randomly generating letters and appending them to the end of string $S$, which is initially empty.
3. If $S$ contains the string chosen by a player, the game ends and that player wins.

Suppose players 1 and 2 choose strings $A$ and $B$ respectively. If player 1 can defeat player 2 with higher probability, we write $A > B$. At first glance, Xiao Yu'er thought that if $A > B$ and $B > C$ then $A > C$. However, the opposite is true: there exist strings $A, B, C$ such that $A > B$, $B > C$, and $C > A$.

Xiao Yu'er was fascinated by this counterintuitive phenomenon. From the literature, he learned that this is called the "non-transitivity paradox", which often appears in many imperfect-information games (such as military chess). But how does it arise? Xiao Yu'er decided to design a game in which it is easy to find non-transitive examples, to better understand "non-transitivity". Of course, the simpler the game, the deeper the idea; thus Xiao Yu'er thought of the simplest dice-rolling game.

The game is as follows. Assume there are $n$ dice $D_1, \dots, D_n$, each with $m$ faces. Each face is labeled with a positive integer from $1$ to $n \times m$, and across all dice, the $n \times m$ faces have pairwise distinct labels. If the above labeling requirement is satisfied and each face is equally likely to be rolled, such $n$ dice are called a set of "good dice". At the start of the game, the two players choose two dice $D_i$ and $D_j$; they each roll once and compare the numbers on the rolled faces, and the larger number wins.

Xiao Yu'er asks you to design a set of "good dice" such that for every die $D_i$, it always beats $D_{a_i}$. Here, "beat" means the probability that the player choosing the former wins exceeds $1/2$; $a_1, a_2, \dots, a_n$ are the input integers in $1 \sim n$.

Input Format

The first line contains two integers $n, m$. The second line contains $n$ integers, namely $a_1, a_2, \dots, a_n$.

Output Format

Output $n$ lines, each containing $m$ distinct integers in $1 \sim n \times m$, separated by spaces.

If there are multiple solutions, output any one of them. If there is no solution, output a single integer $0$.

3 3
2 3 1

1 6 8
3 5 7
2 4 9

3 4
2 1 2

0

3 4
2 3 1

1 3 10 11
2 7 8 9
4 5 6 12

4 4
4 1 2 3

1 11 8 14
12 15 2 5
3 6 16 9
4 10 13 7

Hint

• 30% of the testdata satisfies $n, m \le 10$.
• 100% of the testdata satisfies $3 \le n, m \le 200$.

Thanks to @cn: 苏卿念 for providing the SPJ.

Translated by ChatGPT 5