신전 미로

평생에 걸친 꼼꼼한 연구와 고대 유적 탐사 끝에, Carla는 마침내 잃어버렸던 태양신의 신전을 찾아냈다! 그녀는 밧줄 사다리를 타고 지하 신전으로 내려가는데, 사다리에서 내려선 순간 자신이 거대한 정사각형 미로 한가운데에 서 있다는 것을 알게 된다. 하지만 걱정할 필요는 없다. Carla는 이 신전을 수년간 연구해 왔고, 미로의 상세한 격자 지도를 챙겨 왔기 때문이다. 주변을 살펴보고 그녀는 지도에서 @로 표시된, 자신이 서 있는 정확한 위치를 알아낸다. 이제 그녀는 지도에서 $로 표시된 빛나는 태양석이라는 보물을 찾으려 한다. 물론 태양신의 신전에는 #로 표시된 막는 벽이 널려 있어 미로를 여러 구역으로 나눈다. 미로에는 또한 고대 룬 문자가 새겨진 수많은 문이 있다. Carla는 미로 곳곳에 특정 룬 문자가 새겨진 문을 모두 내릴 수 있는 특별한 레버가 흩어져 있다는 것을 알고 있다. 지도에서 레버는 소문자로, 문은 대문자로 나타낸다. 각 레버는 자신과 같은 글자의 문을 모두 내린다. 예를 들어 a 레버는 모든 A 문을 내린다.

Carla는 서둘러 태양석을 찾아야 한다. 그녀는 이미 태양석을 박물관에 넘기는 대신 경매에 팔아넘기려는 도둑 떼에게 쫓기고 있다! Carla가 현재 위치에서 빛나는 태양석까지 가는 가장 빠른 경로를 찾도록 도와주자!

Carla는 현재 위치한 칸에서 바로 위, 아래, 왼쪽, 오른쪽으로 이웃한 칸으로만 이동할 수 있다. 빈 공간, 레버, 이미 내려간 문은 지나갈 수 있다. Carla는 미로의 경계를 벗어날 수 없다(미로 전체가 단단한 암석으로 둘러싸여 있다). Carla가 레버 칸을 지나가면 레버를 자동으로 당긴다. 같은 글자의 문과 레버가 여러 개 있을 수 있다. 어떤 글자가 적힌 레버를 하나라도 당기면 그 글자에 해당하는 문이 모두 내려간다.

첫째 줄에 정수 $n$ ($3 \leq n \leq 2 \cdot 10^2$)이 주어진다. 이는 지하 미로의 가로 및 세로 칸 수이다. 다음 $n$개의 줄에는 각각 $n$개의 문자가 주어지며, 각 문자는 위에서 설명한 대로 미로의 한 칸을 나타낸다. 미로의 빈 칸은 . 문자로 나타낸다. 미로에서 레버와 문을 표시하는 룬 문자는 최대 $10$가지이므로, 입력에서 레버와 문을 나타내는 데에는 문자 a부터 j까지와 A부터 J까지만 사용된다. 격자는 유효한 문자로만 이루어지며, $와 @를 각각 정확히 하나씩 포함한다.

Carla가 빛나는 태양석에 도달하기 위해 이동해야 하는 최소 걸음 수(칸 사이 이동 횟수)를 출력한다. 태양석에 도달할 수 있는 경로가 없으면 IMPOSSIBLE을 대신 출력한다.