URI Online Judge | 1376

Irmãos

Por Jorge Teran Bolívia
Timelimit: 2

Na terra de ACM governou um grande rei que se tornou obcecado com a ordem. O reino tinha um forma retangular, e o rei dividiu o território em uma grade de pequenos municípios retangulares. Antes de morrer, o rei distribuiu os municípios entre seus filhos.

No entanto, ele não tinha conhecimento de que seus filhos tinham desenvolvido uma rivalidade estranha: O primeiro herdeiro odiava o segundo herdeiro, mas não o resto, o segundo herdeiro odiava o terceiro herdeiro, mas não o resto, e assim diante... Finalmente, o último herdeiro odiava o primeiro herdeiro, mas não os outros herdeiros.

Assim que o rei morreu, a estranha rivalidade entre os filhos do rei desencadeou uma generalizada guerra no reino. Ataques só ocorreram entre pares de municípios adjacentes (municípios adjacentes são aqueles que partilham uma fronteira vertical ou horizontal). Um município X atacava um município Y adjacente sempre que o proprietário do X odiava o proprietário de Y. O município que foi atacado sempre era conquistado pelo irmão atacante. Por uma regra de honra todos os ataques foram realizados ao mesmo tempo, e um conjunto de ataques simultâneos foi chamado de batalha. Depois de um certo número de batalhas, os filhos sobreviventes fizeram uma trégua e nunca lutaram novamente. Por exemplo, se o rei tinha três filhos, chamados 0, 1 e 2, a figura abaixo mostra o que acontece na primeira batalha de uma dada distribuição inicial de terras:

Você foi contratado para ajudar um historiador de ACM a determinar, dado o número de herdeiros, a inicial distribuição de terras e o número de batalhas, como ficou a distribuição de terras após todas as batalhas.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém quatro inteiros N, R, C e K, separados por espaços simples. N é o número de sucessores (2 ≤ N ≤ 100), R e C são a dimensões do reino (2 ≤ R, C ≤ 100), e K é o número de batalhas (1 ≤ K ≤ 100). Herdeiros são identificados por números inteiros sequenciais a partir de zero (0 é o primeiro herdeiro, 1 é o segundo herdeiro, ..., N - 1 é o último herdeiro). Cada uma das próximas linhas R contém C inteiros Hr,c separado por espaços simples, que representam a distribuição de terras inicial: Hr,c é o proprietário inicial do município em r linha e coluna c (0 ≤ Hr,cN - 1).

O último caso de teste é seguido por uma linha contendo quatro zeros separados por espaços.

Saída

Para cada caso de teste, seu programa deve imprimir R linhas com C inteiros cada, separados por um único espaço no mesmo formato que a entrada, o que representa a distribuição de terras, após todas as batalhas.

Exemplo de Entrada Exemplo de Saída

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

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