신호등

아래 <그림 1>에서 보인 것처럼 $N\times M$ 크기의 격자 모양으로 구성된 도로가 있고 각 교차점의 좌표도 아래의 그림과 같다.

각 교차점에는 신호등이 있는데 이는 자동차가 움직일 수 있는 방향을 가리키고 있다. 이 신호등의 방향은 처음에는 무작위로 주어진다. 그리고 각 신호등의 방향 표시는 시간이 $1$ 지날 때마다 반시계방향으로 90º 회전한다. <그림 1>에서 보인 신호등은 시각 $0$일 때의 상황이며, 시각 $1$일 때의 상황은 <그림 2>와 같다.

그림에선 가로길의 개수가 $5$개, 세로길의 개수가 $7$개이다. 따라서, 이 격자의 크기는 $5\times 7$이며, 왼쪽 위 모서리의 좌표는 $(0, 0)$ 이고, 오른쪽 아래 모서리의 좌표는 $(4, 6)$이 된다.

격자의 한 칸을 자동차가 움직이는 데 걸리는 시간은 $1$이다. 그리고 격자의 각 교차점에서는 차는 신호가 바뀌길 기다리며, 대기하거나 또는 화살표가 가리키는 방향으로 움직일 수 있다. 자동차가 진행 방향을 바꾸는 데 따른 소비되는 시간은 0으로 간주한다. 만약 화살표가 가리키는 방향으로 길이 없으면 그 방향으로 자동차가 움직일 수 없다.

각 신호등에 관한 정보가 미리 주어져 있을 때 (즉, 운전자는 모든 신호등 방향에 대해 미리 알고 있다), 시각 $k$에서 격자의 $(r, c)$ 지점을 출발한 차가 각각의 다른 모든 지점마다 가장 일찍 도착하는 시각을 구하려고 한다.

입력 형식

첫 줄에 격자의 크기를 나타내는 두 정수 $N$과 $M$ ($3 \le N, M \le 400$), 차의 출발 시각을 나타내는 정수 $k$ ($1 \le k \le 1\,000$), 차의 출발 지점의 좌표를 나타내는 두 정수 $r$, $c$ ($0 \le r < N$; $0 \le c < M$)가 공백으로 구분되어 주어진다.

그다음 $N$개의 줄에 걸쳐 각각에 $M$개의 정수 $d$ ($0 \le d \le 3$)가 주어지는데 각 값은 격자의 각 교차점에 배치된 신호등의 방향을 나타낸다. 입력에 주어지는 신호등의 방향은 시각 $0$을 기준으로 설정된 것이다. $d$ 값과 신호등의 방향은 아래와 같다.

• $0$: 오른쪽 방향
• $1$: 위 방향
• $2$: 왼쪽 방향
• $3$: 아래 방향

출력 형식

$N$개의 줄에 걸쳐 답을 출력한다.

각 줄에는 $M$개의 정수가 공백으로 구분되어 출력되어야 하며, 각 결과에서 $i$번째 줄, $j$번째 칸에 출력된 수는 시각 $k$에 격자의 $(r, c)$ 지점을 출발한 차가 $(i-1, j-1)$ 지점에 가장 일찍 도착하는 시각이다.

예제 1

5 9 2 4 7
0 2 3 3 2 1 2 0 1
3 2 2 3 3 0 3 1 2
2 3 1 3 1 1 0 2 3
2 0 0 0 3 0 1 0 1
0 2 0 0 2 3 2 1 2

21 20 20 17 14 13 11 9 12
21 17 16 15 15 12 10 8 11
20 18 16 14 14 11 9 6 7
22 19 15 12 11 10 7 5 8
21 19 15 13 12 9 6 2 4

예제 2

4 12 4 1 2
1 0 3 0 2 3 3 2 1 2 0 1
2 0 3 2 2 1 3 3 0 3 1 2
1 2 2 3 1 3 1 0 1 0 2 3
1 2 0 1 0 0 3 0 2 1 0 1

11 8 7 8 8 11 14 15 19 20 23 25
11 8 4 6 7 11 12 14 18 21 22 24
9 8 5 7 10 12 13 16 17 20 21 23
9 7 6 9 11 13 15 18 19 23 22 25

채점 방식

이 문제는 모든 케이스를 맞추는 경우에만 만점을 받고, 그렇지 않으면 $0$점을 받는다.

해설