Brothers

A great King ruled a kingdom shaped like a rectangle. Before he died, he divided the territory into a grid of small rectangular counties and distributed them among his sons.

The King did not know that his sons had a peculiar rivalry: heir $0$ hated heir $1$, heir $1$ hated heir $2$, and so on; the last heir, $N-1$, hated heir $0$. Each heir hated exactly one other heir and no one else, so in general heir $i$ hated heir $(i+1) \bmod N$.

When the King died, war broke out. Two counties are adjacent if they share a horizontal or vertical border. During an attack, a county $X$ conquers an adjacent county $Y$ whenever the owner of $X$ hates the owner of $Y$, and the conquered county then belongs to the attacker. All attacks happen simultaneously, and one round of simultaneous attacks is called a battle.

Because the only heir who hates the owner $v$ of a county is heir $(v-1) \bmod N$, every county that is attacked is conquered by that same heir. Equivalently: in each battle, a county currently owned by $v$ becomes owned by $(v-1) \bmod N$ if at least one of its orthogonal (up, down, left, right) neighbors is owned by $(v-1) \bmod N$; otherwise it keeps owner $v$.

Given the number of heirs, the initial land distribution, and the number of battles, determine the land distribution after all battles have taken place. For example, with three heirs ($N = 3$) a single battle transforms the map according to the rule above.

The input contains several test cases. The first line of a test case contains four integers $N$, $R$, $C$ and $K$ separated by single spaces: $N$ is the number of heirs ($2 \le N \le 100$), $R$ and $C$ are the dimensions of the kingdom ($2 \le R, C \le 100$), and $K$ is the number of battles ($1 \le K \le 100$). Heirs are numbered from $0$ (the first heir) to $N-1$ (the last heir).

Each of the next $R$ lines contains $C$ integers $H_{r,c}$ separated by single spaces: $H_{r,c}$ is the initial owner of the county in row $r$ and column $c$ ($0 \le H_{r,c} \le N-1$).

The last test case is followed by a line containing four zeros separated by single spaces.

For each test case, print $R$ lines with $C$ integers each, separated by single spaces, in the same format as the input, representing the land distribution after all $K$ battles.