[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个骰子D1~Dn,每个骰子有m个面。每个面上标有一个1~n×m的正整数,并且所有骰子的所有n×m个面上的数字各不相同。满足这条编号要求,并且每个面被随到的概率相等的,这样的n个骰子称为一组“好骰子”。游戏开始时,两个玩家分别选两个骰子Di和Dj,各掷一次来比较掷出来那一面的数值,数大的获胜。 小鱼儿请你帮忙设计一组“好骰子”,使得对任意一个骰子Di,它总能战胜Dai。此处战胜是指选择前者的玩家获胜的概率超过1/2;a1~an为输入的1~n的正整数。

输入输出格式

输入格式


第一行为两个整数n, m。第二行有n个整数,为a1,a2, …, an。

输出格式


包含n行,每行m个1~n×m的正整数,各不相同,以空格分开。 如果有多解,输出任意一组解;如果无解,输出一个整数0。

输入输出样例

输入样例 #1

3 4
2 1 2

输出样例 #1

0

说明

30%的数据满足n, m≤10 100%的数据满足3≤n, m≤200 感谢 @cn:苏卿念 提供spj