고렐리안 도시의 가장 빠른 경로

고렐리안(Gorelian)은 재미 삼아 우주를 돌아다니며 새로운 세계를 정복하는 호전적인 종족이다. 폭력적이면서도 유희를 즐기는 성향 탓에, 지도자들을 안전하게 지키는 일은 매우 중대한 관심사다. 고렐리안 보안 계획의 하나는 매일 도시의 교통 패턴을 바꾸어, 모든 고렐리안 정부 관료를 가능한 한 가장 빠른 경로로 정부 청사까지 이동시키는 것이다.

다행히 고렐리안 교통부 장관(바로 당신)에게 유리하게도, 모든 고렐리안 도시는 직사각형 격자 형태의 블록으로 이루어져 있다. 각 블록은 한 변의 길이가 $2520$ 렐(rel) 인 정사각형이다(렐 은 고렐리안 공식 거리 단위다). 인접한 두 교차로 사이의 제한 속도는 일정하며, $1$ 이상 $9$ 이하의 정수 렐/블립(blip) 이다(블립 은 고렐리안 공식 시간 단위다). 고렐리안은 분수(소수)를 금지했기 때문에 제한 속도는 항상 정수다. 블록의 길이가 정확히 $2520$ 렐 인 이유가 바로 이것인데, $2520$ 은 $1$ 부터 $9$ 까지의 정수의 최소공배수이므로 인접한 두 교차로 사이를 이동하는 데 걸리는 시간은 항상 정수 블립이 된다.

모든 고렐리안 도시에서 정부 관사는 항상 북서쪽 모서리에, 정부 청사는 항상 남동쪽 모서리에 있다. 두 교차로를 잇는 도로는 일방통행이거나 양방향 통행일 수 있고, 혹은 보수 공사로 폐쇄되어 있을 수도 있다. 어떤 도시의 제한 속도, 통행 방향, 폐쇄 정보가 주어질 때, 정부 관사(북서쪽 모서리)에서 정부 청사(남동쪽 모서리)까지의 가장 빠른 경로를 구하여라. 도로는 항상 게시된 제한 속도로만 달리며, 모퉁이를 도는 데에는 시간이 걸리지 않는다. 만약 경로가 존재하지 않으면 고렐리안 공식 임시 공휴일이 선포되고 관료들은 그날 하루를 쉰다.

예를 들어 어떤 도시에서는 가장 빠른 경로가 $1715$ 블립이다. 다음 날 유일한 변화가 폐쇄되었던 하나의 도로를 속도 $9$ 렐/블립의 양방향 통행으로 다시 여는 것뿐이라면, 가장 빠른 경로는 $1295$ 블립이 된다. 반대로 세 개의 일방통행 도로를 남향에서 북향으로 뒤집는다면(폐쇄된 도로는 그대로 폐쇄), 어떤 경로도 존재하지 않아 그날은 공휴일이 된다.

입력은 여러 개의 도시로 구성되며, 각 도시에 대해 경로가 존재한다면 가장 빠른 경로를 구해야 한다.

각 도시의 첫 줄에는 두 정수가 주어지는데, 각각 세로 방향 블록 수와 가로 방향 블록 수이다. 가장 작은 도시는 $1 \times 1$ 블록이고 가장 큰 도시는 $20 \times 20$ 블록이다.

그 다음부터는 도로 정보가 북쪽에서 남쪽으로, 한 줄에 도로 세그먼트 한 행씩 주어진다.

• 가장 북쪽의 동서 방향 도로 세그먼트 행
• 그 다음, 가장 북쪽의 남북 방향 도로 세그먼트 행
• 그 다음, 동서 방향 도로 행
• 그 다음, 남북 방향 도로 행
• ... 이런 식으로 가장 남쪽의 동서 방향 도로 행까지 이어진다.

각 행에서 세그먼트는 서쪽에서 동쪽 순으로 나열된다. 각 세그먼트는 $0$ 이상 $9$ 이하의 정수 제한 속도와 방향 기호로 이루어지며, 모든 값은 하나의 공백으로 구분된다. 제한 속도 $0$ 은 도로가 폐쇄되었음을 뜻하며, 항상 뒤에 * 가 붙는다.

동서 방향 도로의 기호는 다음과 같다.

• * — 양방향 통행 가능
• < — 동쪽에서 서쪽으로만 통행 가능
• > — 서쪽에서 동쪽으로만 통행 가능

남북 방향 도로의 기호는 다음과 같다.

• * — 양방향 통행 가능
• v — 북쪽에서 남쪽으로만 통행 가능
• ^ — 남쪽에서 북쪽으로만 통행 가능

도시 목록은 크기로 $0$ $0$ 이 주어지는 줄로 끝난다.

각 도시마다 한 줄을 출력한다. 경로가 존재하면 가장 빠른 경로의 블립 수(정수)와 공백, 그리고 단어 blips 를 출력한다. 경로가 존재하지 않으면 단어 Holiday 를 출력한다.