도시 길찾기

미국의 도시는 대부분 아주 단순한 계획에 따라 만든다. 애비뉴는 남북으로, 스트리트는 동서로 뻗어 정사각형 블록을 둘러싼다. 애비뉴와 스트리트에는 번호가 붙어 있고, 번호는 서쪽으로 갈수록 그리고 남쪽으로 갈수록 커진다. 블록 한 변에는 도로 양쪽에 진입로가 50개씩 있고, 한쪽은 00번부터 98번까지, 반대쪽은 01번부터 99번까지 쓴다. $2k$번과 $2k+1$번은 도로를 사이에 두고 마주 보며 같은 구획 하나를 이루므로, 블록 한 변은 구획 50개로 나뉜다. 집 번호는 스트리트와 애비뉴 번호가 커지는 방향과 같은 방향으로 커진다. 번호가 커지는 방향으로 달리면 홀수 번호가 오른쪽에 있다.

16번 스트리트 1288번지, 즉 S16 1288은 16번 스트리트에서 12번 애비뉴의 서쪽이자 13번 애비뉴의 동쪽에 있고, 동쪽으로 달릴 때 오른쪽에 있다. A11 1543은 11번 애비뉴에서 15번 스트리트의 남쪽이자 16번 스트리트의 북쪽에 있고, 남쪽으로 달릴 때 오른쪽에 있다. 두 곳 모두 아래 지도에 표시했다.

조용한 주택가는 애비뉴와 스트리트 일부를 끊어 놓는 간단한 방법으로 만든다. 지도에서 보듯이 중간이 끊긴 자리가 있어도 애비뉴와 스트리트는 이름을 그대로 유지한다. 주소만 보면 어디로 가야 하는지 정확히 알 수 있어서 이런 도시에서 길을 잃기는 어렵다. 다만 어느 구간이 끊겼는지 모르면 막다른 길로 들어가 시간을 많이 허비한다.

도시에서 끊긴 구간의 정보를 읽고, 이어서 주소 쌍을 여러 개 읽는 프로그램을 작성하라. 주소는 집이 아니라 진입로 하나를 가리킨다고 본다. 각 주소 쌍마다 규칙을 지키는 경로 중 가장 짧은 경로로 두 진입로 사이의 거리를 구한다. 거리는 달리는 동안 내가 달리는 쪽 도로변에서 지나치는 진입로의 개수이고, 출발 진입로와 도착 진입로는 세지 않는다. 다음을 가정한다.

차는 도로의 오른쪽으로 달린다.
교차로가 아닌 자리에서는 맞은편 차선을 가로지를 수 없다. 즉 진입로에 들어가거나 진입로에서 나올 때는 반드시 우회전해야 한다.
진입로는 각 구획의 한가운데에 있다.
유턴은 막다른 길 끝에서만 할 수 있다.
스트리트와 애비뉴의 번호는 00번부터 49번까지이고 그 바깥에는 도로가 없다. 다만 가장 바깥 도로에도 양쪽에 진입로가 있다.
모퉁이에 걸친 구획에는 진입로가 두 개 있다.
어떤 두 진입로 사이에도 경로가 존재한다.

입력은 끊긴 도로 부분과 주소 부분으로 나뉘고, 각 부분은 # 한 글자만 있는 줄로 끝난다.

끊긴 도로 부분의 각 줄에는 도로 식별자 하나와 집 번호 두 개가 있다. 도로 식별자는 애비뉴를 뜻하는 A 또는 스트리트를 뜻하는 S 뒤에 00 이상 49 이하의 번호를 붙인 것이다. 집 번호는 0000 이상 4898 이하의 짝수다. 그 도로에서 두 번호가 있는 자리를 포함해 두 번호 사이의 구간은 통행할 수 없다. 끊긴 자리는 도로를 가로질러 그대로 이어지므로, 1612번을 지날 수 없으면 1613번도 지날 수 없다. 끊긴 구간은 진입로가 아니라 구획의 경계에서 시작해 구획의 경계에서 끝난다. 한 줄의 각 부분은 공백 하나로 구분한다.

주소 부분의 각 줄에는 주소가 두 개 있다. 주소는 도로 식별자 뒤에 0000 이상 4899 이하의 번호를 붙인 것이다. 한 줄의 각 부분은 공백 하나로 구분한다.

도시 길찾기

문제

입력

출력