미친 아두이노

종수는 아두이노로 "Robots"라는 게임을 만들었다. 종수는 아두이노 한 대를 조종하며, 자신을 쫓아오는 미친 아두이노들을 피해 다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 조금씩 다가오지만, 그 움직임은 완전히 예측할 수 있다.

게임은 $R \times C$ 크기의 보드 위에서 진행되며, 한 턴은 다음 다섯 단계로 이루어진다. 이 과정을 주어진 방향 문자열의 길이만큼 반복한다.

먼저 종수가 자신의 아두이노를 8방향(상하좌우와 대각선) 중 한 칸으로 옮기거나, 제자리에 그대로 둔다.
종수의 아두이노가 미친 아두이노가 있는 칸으로 이동하면 게임이 끝나고, 종수가 진다.
각 미친 아두이노는 8방향 중에서 종수의 아두이노와 가장 가까워지는 방향으로 한 칸 이동한다. 종수의 위치를 $(r_1, s_1)$ , 미친 아두이노의 위치를 $(r_2, s_2)$ 라고 하면, 이동한 뒤 $|r_1 - r_2| + |s_1 - s_2|$ 가 가장 작아지는 방향을 고른다.
미친 아두이노가 종수의 아두이노가 있는 칸으로 이동하면 게임이 끝나고, 종수가 진다.
서로 다른 두 대 이상의 미친 아두이노가 같은 칸에 모이면 큰 폭발이 일어나, 그 칸에 있던 미친 아두이노가 모두 파괴된다.

종수의 시작 위치, 미친 아두이노들의 위치, 그리고 종수가 각 턴에 움직이려는 방향이 주어진다. 주어진 방향대로 종수가 움직였을 때 최종 보드의 상태를 구하여라. 도중에 게임에서 지게 되면, 몇 번째 이동에서 지는지를 구한다.

첫째 줄에 보드의 크기 $R$ 과 $C$ 가 주어진다. ( $1 \le R, C \le 100$ )

다음 $R$ 개의 줄에는 각각 $C$ 개의 문자로 보드의 상태가 주어진다. .는 빈 칸, R은 미친 아두이노, I는 종수의 아두이노를 나타낸다.

마지막 줄에는 길이가 $100$ 이하인 문자열이 주어지며, 종수가 각 턴에 움직이려는 방향을 순서대로 나타낸다. 방향은 숫자 키패드와 같은 배치를 따른다. 5는 제자리에 머무는 것을 뜻하고, 나머지 숫자는 아래 방향을 뜻한다. 위쪽은 행 번호가 줄어드는 방향이다.

7 = ↖   8 = ↑   9 = ↗
4 = ←   5 = 제자리   6 = →
1 = ↙   2 = ↓   3 = ↘

방향 키패드

종수가 보드 밖으로 나가는 입력은 주어지지 않는다.

도중에 게임이 끝나는 경우에는 kraj X를 출력한다. $X$ 는 게임이 끝나는 그 턴을 포함하여, 종수가 이동을 시도한 횟수이다. 즉 $K$ 번째 방향을 처리하는 도중에 게임이 끝나면 $X$ 는 $K$ 이다.

모든 방향을 처리할 때까지 게임이 끝나지 않으면, 입력과 같은 형식으로 최종 보드의 상태를 출력한다.