Nontransitive Dice Design

Little Yuery is a mathematical genius. In his research on games with a nontransitive paradox, he discovered an interesting dice game. In this game, there are n dice (denoted D₁, D₂, …, D_n) each having m faces. Each face is marked with a distinct integer from 1 to n×m (each number appears exactly once among all dice), and every face is equally likely to appear when rolled. Such a set of dice is called a set of "good dice."

The game is played as follows. Two players each choose one die. They roll their chosen dice once; the player whose outcome is larger wins. For any two dice D_i and D_j, we say that D_i beats D_j if the probability that a roll of D_i gives a higher number than a roll of D_j is greater than 1/2.

Given an array of n positive integers a₁,a₂,…,a_n (with each a_i in {1,…,n}) specifying that die D_i should beat die D_ai, Little Yuery wishes to design a set of good dice so that for every i (1 ≤ i ≤ n) the winning probability

$$\Pr\{D_i > D_{a_i}\} > \frac12.$$

Note on the input: It can be proved that if n > 1 one must have a₁ = 1 (so that D₁ is compared with itself) and for every 2 ≤ i ≤ n, a_i < i. For the purpose of this problem, you may assume the input satisfies these conditions. (Since it is impossible for any die to beat itself, the requirement for i = 1 is considered to be vacuously true.)

Your task is to output any valid set of good dice. In other words, assign the numbers 1, 2, …, n×m into an n × m matrix such that if we denote the i-th row as the faces of D_i, then for every 2 ≤ i ≤ n, when D_i is compared to D_ai the number of winning pairs (over all m×m pairs when rolling the two dice) is strictly more than \(\frac{m^2}{2}\>.

A simple solution construction: Under the assumption that for every i ≥ 2, a_i < i, one may simply assign

$$D_i = \{i,\; i+n,\; i+2n,\; \dots,\; i+(m-1)n\}, \quad 1 \le i \le n. $$

Observe that for any two dice D_i and D_j with i > j, every face of D_i is greater than the corresponding face of D_j in the same "position". In fact, when comparing D_i with D_j, one may easily verify that D_i wins every pair if the faces are paired by their positions. In the cross‐comparison of all m × m pairs, it turns out that the win probability is 1 (which is greater than 1/2). (For i = 1 the input guarantees a₁ = 1, and we consider this case to be vacuously satisfied.)

Your submission is to output any valid dice configuration (if more than one exists, any one will be accepted).

inputFormat

The first line contains two positive integers n and m (n > 1, m is odd), denoting the number of dice and the number of faces on each die. The second line contains n integers a₁, a₂, …, a_n (1 ≤ a_i ≤ n). It is guaranteed that a₁ = 1 and for every 2 ≤ i ≤ n, a_i < i.

outputFormat

Output n lines. The i-th line should contain m space-separated integers – the numbers on the faces of die D_i. The numbers used across all dice must be exactly 1, 2, …, n×m, each appearing exactly once. The configuration must satisfy that for every 2 ≤ i ≤ n, the probability that a roll of D_i yields a number greater than a roll of D_ai is greater than 1/2.

sample

4 3
1 1 1 2

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

</p>