레이저 체스

Fredrik과 Abdullah가 레이저 체스 한 판을 두고 있다. 게임은 격자판 위에서 진행되며, 목표는 상대 킹에 레이저 광선을 쏘는 것이다. Abdullah에게는 버튼을 누르면 위, 아래, 오른쪽, 왼쪽 네 방향으로 레이저를 쏘는 공격 기물이 있다. 공격 기물은 격자에서 A로 표시한다. Fredrik의 킹은 K로 표시한다. 격자에는 거울 기물도 있으며 o로 표시한다. 레이저가 거울 기물에 닿으면 빛이 네 방향으로 튕겨 나간다.

지금 판은 Abdullah가 레이저 버튼만 누르면 이기는 상황이다. 이를 막기 위해 Fredrik이 판 위에 연막탄을 놓았고, 이는 R로 표시한다. 연막이 있는 칸은 레이저가 지나갈 수 없다. 연막은 매초 인접한 네 칸으로 퍼진다. 공격 기물이나 킹이 연막 안에 있으면 Abdullah는 이길 수 없다.

버튼을 눌러도 Abdullah가 더 이상 이기지 못하게 되기까지 몇 초가 걸리는가? 다시 말해, 공격 기물에서 나온 레이저가 킹에 닿지 않게 될 때까지 연막이 몇 초 동안 퍼지는지 구하라.

처음 상태에서는 연막을 지나지 않고 공격 기물에서 킹까지 레이저가 닿는다는 것이 보장된다.

첫 줄에 격자의 행 수 $R$과 열 수 $C$가 주어진다 ($1\le R, 1 \le C, R\times C \le 40 000$).

이어지는 $R$개의 줄이 판의 모습을 나타낸다. $i$번째 줄은 $C$개의 문자로 이루어지며, 각 문자는 다음 중 하나이다.

• . 빈 칸
• o 거울 기물
• R 연막탄
• A 공격 기물
• K 킹

A와 K는 각각 정확히 한 번씩 나타나고, R은 적어도 한 번 나타난다. 처음에는 연막을 지나지 않고 공격 기물에서 킹까지 레이저가 도달한다는 것이 보장된다.

레이저가 킹에 더 이상 닿지 않게 되기까지 걸리는 시간(초)을 양의 정수 하나로 출력한다.

첫 번째 테스트 케이스의 1초 후 모습이다.

두 번째 테스트 케이스의 3초 후 모습이다.

세 번째 테스트 케이스의 2초 후 모습이다.