[SCOI2009] 骰子的学问

题目描述

小鱼儿是个数学天才。一天晚上他研究一个和字符串有关的 penney-ante游戏。游戏的规则如下：

1．有两个玩家，开始时每人选择一个长度相同的字符串；

2．一个字符生成器不断的随机生成字母添加到字符串 $S$ 的末尾，$S$ 初始为空串；

3．如果 $S$ 包含了某个玩家选择的字符串则游戏结束，该玩家获胜。

假设玩家1和玩家2分别选择了两个字符串 $A$ 和 $B$，如果玩家1可以以较大概率战胜玩家2，我们记作 $A>B$。 咋一看来，小鱼儿觉得如果 $A>B$ 且 $B>C$ 则 $A>C$。可事实恰好相反，存在字符串 $A, B, C$ 使得$A>B, B>C, C>A$。

小鱼儿被这种戏的一个反常现象所吸引，通过查阅资料，他了解到这种现象被称为“非传递性悖论”，在许多非完全信息游戏（比如军棋）中，经常会有这样的例子。可是它到底是如何产生的呢？小鱼儿决定设计一种游戏，从中可以容易的找到非传递的例子，以便更清楚的认识“非传递性”。当然，这样的游戏越简单道理越深刻，于是小鱼儿想起了最简单的掷骰子游戏……

这个游戏是这样的，假设有n个骰子 $D_1\sim D_n$，每个骰子有 $m$ 个面。每个面上标有一个 $n\times m$ 的正整数，并且所有骰子的所有 $n\times m$ 个面上的数字各不相同。满足这条编号要求，并且每个面被随到的概率相等的，这样的 $n$ 个骰子称为一组“好骰子”。游戏开始时，两个玩家分别选两个骰子 $D_i$ 和 $D_j$，各掷一次来比较掷出来那一面的数值，数大的获胜。

小鱼儿请你帮忙设计一组“好骰子”，使得对任意一个骰子 $D_i$，它总能战胜 $D_{a_i}$。此处战胜是指选择前者的玩家获胜的概率超过$\frac{1}{2}$；$a_1\sim a_n$为输入的 $1\sim n$ 的正整数。

输入格式

第一行为两个整数 $n, m$。第二行有n个整数，为 $a_1,a_2,\cdots, a_n$。

输出格式

包含 $n$ 行，每行 $m$ 个 在 $[1,n\times m]$ 中的正整数，各不相同，以空格分开。

如果有多解，输出任意一组解；如果无解，输出一个整数0。

样例 #1

样例输入 #1

3 4
2 1 2

样例输出 #1

0

提示

30%的数据满足 $n, m≤10$

100%的数据满足 $3≤n, m≤200$

感谢 @cn：苏卿念 提供spj