수수께끼의 던전

아쿠아 카노라 미스티카 왕국은 매우 부유하고 평화로운 나라지만, 왕국 주변에는 사람을 죽이는 사악한 몬스터가 많다. 그래서 왕은 너에게 우두머리 몬스터를 처치하라는 명령을 내렸다.

너는 몬스터가 사는 던전에 도착했다. 던전은 정사각형 칸들의 격자로 이루어져 있다. 너는 던전을 상하좌우로 이동하며 탐험했다. 마침내 몬스터를 찾아 싸워 처치했다.

이제 던전을 빠져나와 집으로 돌아가려 한다. 그런데 몬스터를 처치한 뒤에야 던전에 나타난 이상한 카펫과 큰 바위들을 발견했다. 그것들은 몬스터가 죽기 직전에 마지막으로 건 마법 때문이다! 바위는 각각 한 칸 전체를 차지하며, 그 칸으로는 지나갈 수 없다. 카펫도 각각 정확히 한 칸을 덮는다. 바위에는 알파벳 대문자, 카펫에는 알파벳 소문자 라벨이 붙어 있다. 바위와 카펫 중에는 같은 라벨을 가진 것도 있다.

던전을 돌아다니면서 너는 다음과 같은 현상을 관찰했다. 카펫이 덮은 칸에 들어가면, 대응하는 글자의 라벨이 붙은 바위들(예를 들어 'a' 카펫에 대해서는 'A' 바위들)이 모두 사라진다. 사라진 뒤에는 바위가 사라진 칸으로 들어갈 수 있지만, 같은 카펫 칸에 다시 들어가거나 같은 라벨의 다른 카펫 칸에 들어가면 바위가 되살아나 다시 들어가는 것을 막는다. 바위가 되살아난 뒤에는 그 바위들을 다시 사라지게 하려면 해당 카펫 칸으로 다시 이동해야 한다.

던전에서 빠져나갈 수 있는가? 빠져나갈 수 있다면 얼마나 빨리 빠져나갈 수 있는가? 당신의 과제는 던전에서 빠져나갈 수 있는지 판정하고, 필요한 최소 시간을 계산하는 프로그램을 작성하는 것이다.

입력은 여러 개의 데이터 세트로 이루어진다.

각 데이터 세트는 두 정수 W와 H (3 ≤ W, H ≤ 30)가 있는 줄로 시작한다. 다음 H개 줄에는 각각 W개의 문자가 있으며, 이는 던전의 지도를 W × H 격자로 나타낸다. 각 문자는 다음 중 하나이다:

• '@'는 현재 당신의 위치,
• '<'는 던전의 출구,
• 소문자는 해당 글자의 라벨이 붙은 카펫이 덮은 칸,
• 대문자는 해당 글자의 라벨이 붙은 바위가 차지한 칸,
• '#'은 벽,
• '.'은 빈 칸이다.

모든 던전은 벽 칸('#')으로 둘러싸여 있으며, '@' 칸과 '<' 칸이 각각 정확히 하나씩 있다. 바위의 대문자 라벨은 최대 여덟 종류, 카펫의 소문자 라벨은 최대 여덟 종류이다.

한 번에 인접한 칸(상하좌우) 중 하나로 1초에 이동할 수 있다. 벽 칸이나 바위 칸으로는 이동할 수 없다.

두 개의 0이 있는 줄이 입력의 끝을 나타내며, 이 줄은 처리하지 않는다.

각 데이터 세트에 대해 '@' 칸에서 '<' 칸으로 이동하는 데 필요한 최소 시간을 초 단위로 한 줄에 출력한다. 빠져나갈 수 없으면 -1을 출력한다.