P2565 [SCOI2009] The Knowledge of Dice

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$.

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

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$.

- 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