2013年7月18日 星期四

12187 - Brothers

王國是個矩形,國王將國土以網格的方式畫分成數個縣,在國王臨死前,他將這些城市分配給他的兒子們。

然而,他不知道他的兒子們發展一套很奇怪的競爭方式:第一位繼承人討厭第二位繼承人,第二位繼承人討厭第三位繼承人 ... 最後一位繼承人討厭第一位繼承人,


不久之後,國王去世了。繼承人將會以奇怪的競爭方式進行國土戰爭,開始攻擊四方的鄰近區域,當繼承人 Y 討厭繼承人 X 時,城市 X 將被相鄰的城市 Y 攻擊,而被攻擊的城市總會被占據。公平起見,所有的攻擊將會同時發生,而每次發生相當於一次戰爭。在一定次數的戰爭後,兒子們將會進行停戰協定,並且不會再次發動戰爭。

例如:國王有三個兒子,標記為 0, 1, 2,如下圖所示,進行第一次戰爭之後的結果:

你將被雇用來決定這場戰爭的最後局面,根據給定繼承人的數量、一開始的國土分布以及會發生幾場戰爭。

Input 

輸入會有多組測資。

每組第一行會有四個整數 N, R, C, K (2 <= N, R, C <= 100, 1 <= K <= 100)。
分別表示有多少繼承人、國土的行和國土的列以及多少場戰爭。

假設繼承人的編號 0 是第一繼承人,1 是第二繼承人 ... 而 N - 1 則是最後繼承人。

接下來會有 R 行,每行上會有 C  個整數 Hr, c(0 <= Hr, c <= N - 1)表示該國土一開始分配給哪個繼承人,最後一行將會有四個零結束程式。


Output 

對於每組測資,輸出 R  行,每行 C 個整數,表示國土最後的分配方式。

Sample Input 

3 4 4 3
0 1 2 0
1 0 2 0
0 1 2 0
0 1 2 2
4 2 3 4
1 0 3 
2 1 2 
8 4 2 1
0 7 
1 6 
2 5 
3 4 
0 0 0 0

Sample Output 

2 2 2 0
2 1 0 1
2 2 2 0
0 2 0 0
1 0 3 
2 1 2 
7 6 
0 5 
1 4 
2 3