두 개의 고리

21XX년, 인류는 외계 생명체와 교신하는 데 성공했다. 지능을 가진 생명체가 살고 있는 행성을 여럿 발견했고, 행성 간 통신을 즐기고 있다. Vegetablia는 그러한 행성 중 하나다. Vegetablia의 주민은 지구의 채소를 닮아서, 존경과 친근함을 담아 Vegetablian이라고 부른다.

어느 날 Vegetablian 친구인 감자 씨가 여자친구 토마토 양과 결혼하기로 했다고 말했다. 그는 이렇게 말했다. “사실대로 말하자면, 우리는 결혼 전에 한 가지를 해야 해.”

“Vegetablia에는 결혼의 전통 의식이 있어. 그 의식에 따르면 결혼하려는 남자와 여자는 결혼식 전에 각자 Vegetablia를 한 바퀴 돌며 견문을 넓혀야 해. 두 사람은 행성의 서로 다른 지점에서 여행을 시작해서 자기 출발점에 돌아올 때까지 계속 앞으로 나아가. 두 사람의 여행 경로가 행성 위의 두 고리와 같아서 이 의식을 두 고리의 맹세라고 부르지.”

“이 의식에 유명한 이야기가 하나 있어. ‘여행 중에 서로 만난 커플은 행복해진다.’ 나도 그렇게 되길 바라지만, 출발점과 출발 방향에 따라 우리가 절대 만날 수 없는 경우도 있다는 걸 깨달았어. 우리가 만날 수 있는지 정말 알고 싶어.”

감자 씨의 좋은 친구로서 당신은 이 문제를 그를 위해 풀려고 한다. 행성 Vegetablia는 단위 구로 보고, 여행 경로는 구를 자르는 평면으로 표현된다. 두 경로가 주어지면 두 경로의 교점의 좌표를 구하라(존재한다면).

입력은 여러 테스트 케이스로 이루어진다.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수가 주어진다.

각 테스트 케이스는 구 위의 서로 다른 두 원에 대한 설명으로 이루어지며, 각 원은 위도/경도 좌표 두 개로 표현된다. 위도/경도 좌표 p1과 p2는 지름이 선분 p1-p2와 일치하는 원을 나타낸다. 각 위도/경도 좌표는 다음과 같이 주어진다.

lat [N|S] long [E|W]

여기서 lat과 long은 각각 점의 위도와 경도(도 단위)이다. 두 번째 토큰(N 또는 S)과 네 번째 토큰(E 또는 W)은 그 점이 어느 반구에 속하는지를 나타낸다. lat과 long의 값은 0 ≤ lat ≤ 90, 0 ≤ long ≤ 180을 만족한다.

각 좌표 표현에서 p1과 p2는 절대 일치하지 않고, 선분 p1-p2는 단위 구의 지름이 아니라고 가정할 수 있다. 또한 입력에서 lat과 long의 값은 정수라고 가정할 수 있다. 교점이 존재한다면 두 개라는 것이 보장된다.

각 테스트 케이스마다 “Case n:” 한 줄을 출력한다. 여기서 n은 테스트 케이스 번호이다. 그 줄 다음에 두 원이 만나지 않으면 “No intersec- tion.”을 출력한다. 그렇지 않으면 교점의 좌표를 입력과 같은 형식으로 출력한다. 값은 소수점 아래 세 자리까지 출력한다. 좌표를 여러 방식으로 나타낼 수 있다면 어느 것이든 좋다. 모든 값은 음수 부호 없이 출력한다.

각 테스트 케이스 사이에 빈 줄을 하나 출력한다.