형제들

어떤 왕이 직사각형 모양의 왕국을 다스리고 있었다. 왕은 죽기 전에 영토를 작은 직사각형 모양의 주(county) 들로 이루어진 격자로 나누고, 이를 아들들에게 나누어 주었다.

왕은 아들들 사이에 독특한 반목이 있다는 것을 알지 못했다. 상속자 $0$번은 $1$번을 미워하고, $1$번은 $2$번을 미워하며, 이렇게 이어져 마지막 상속자 $N-1$번은 $0$번을 미워했다. 각 상속자는 정확히 다른 한 명만 미워했으므로, 일반적으로 상속자 $i$번은 상속자 $(i+1) \bmod N$번을 미워했다.

왕이 죽자 전쟁이 벌어졌다. 두 주는 가로 또는 세로 변을 공유할 때 인접하다고 한다. 공격이 일어나면, 주 $X$의 주인이 인접한 주 $Y$의 주인을 미워하는 경우 $X$는 $Y$를 정복하고, 정복당한 주는 공격자의 소유가 된다. 모든 공격은 동시에 일어나며, 이렇게 동시에 일어나는 한 번의 공격 묶음을 전투라고 부른다.

주인이 $v$인 주를 미워하는 상속자는 오직 $(v-1) \bmod N$번뿐이므로, 공격받는 주는 항상 그 상속자에게 정복된다. 즉, 각 전투에서 현재 주인이 $v$인 주는, 상하좌우로 인접한 주 중 하나라도 주인이 $(v-1) \bmod N$이면 주인이 $(v-1) \bmod N$으로 바뀌고, 그렇지 않으면 주인이 $v$로 유지된다.

상속자의 수, 초기 영토 분포, 전투 횟수가 주어졌을 때, 모든 전투가 끝난 뒤의 영토 분포를 구하라. 예를 들어 상속자가 세 명($N = 3$)일 때, 한 번의 전투는 위 규칙에 따라 지도를 바꾼다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 네 정수 $N$, $R$, $C$, $K$가 하나의 공백으로 구분되어 주어진다. $N$은 상속자의 수($2 \le N \le 100$), $R$과 $C$는 왕국의 크기($2 \le R, C \le 100$), $K$는 전투 횟수($1 \le K \le 100$)이다. 상속자는 $0$번(첫 번째 상속자)부터 $N-1$번(마지막 상속자)까지 번호가 매겨진다.

이어지는 $R$개의 줄에는 각각 $C$개의 정수 $H_{r,c}$가 하나의 공백으로 구분되어 주어진다. $H_{r,c}$는 $r$행 $c$열에 있는 주의 초기 주인이다($0 \le H_{r,c} \le N-1$).

마지막 테스트 케이스 다음에는 네 개의 $0$이 하나의 공백으로 구분된 줄이 주어진다.

각 테스트 케이스에 대해, 모든 $K$번의 전투가 끝난 뒤의 영토 분포를 입력과 같은 형식으로 $R$개의 줄에 각 줄마다 $C$개의 정수를 하나의 공백으로 구분하여 출력하라.