Two Rings

Time Limit : 8 sec, Memory Limit : 131072 KB

Now judge is temporally not available for this problem. We are earnestly making necessary data. Sorry for the inconvenience.

Problem H: Two Rings

In 21XX, human beings have successfully contacted extraterrestrial life forms. We have found several planets where the intelligent life forms are living, and are enjoying interplanetary communication. Vegetablia is one of such planets. Inhabitants of Vegetablia look like vegetables in the Earth, so we call them Vegetablians with full of respects and familiarity towards them.

One day, Mr. Potato, one of your Vegetablian friends, told you that he has decided to get married to his girlfriend, Ms. Tomato. He said, gTo tell the truth, we have to do one thing before our marriage.h

gIn Vegetablia, there is a traditional practice of marriages. According to the practice, a man and a woman who want to get married should separately make a trip around the Vegetablia and broaden their knowledge before their wedding ceremony. Each of them starts a trip from a distinct point on the planet and he/she keeps going forward until he/she reaches his/her start point. This practice is called the vow of two rings because paths of their trips are just like two rings on the planet.h

gThere is a famous gossip on it: ea couple who met each other during the trip will become happy.f I hope that this will come true, but I realized that there are some cases where we can never meet depending on our starting points and starting directions. I really want to know whether we can possibly meet each other or not.h

As a good friend of Mr. Potato, you want to solve this problem for him. The Vegetablia planet is considered to be a unit sphere, and a path of the trip is expressed as a cutting surface of the sphere. Given two paths, your job is to find the coordinates of their intersecting points (if they exist).


The input consists of multiple test cases.

The first line of the input contains an integer which denotes the number of test cases.

Each test case consists of descriptions of two distinct circles on a sphere, each of which is represented by two latitude/longitude coordinates. Two latitude/longitude coordinates p1 and p2 indicate a circle whose diameter coincides with the line segment p1-p2. Each latitude/longitude coordinate is given as follows:

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

where lat and long are latitude and longitude of a point in degrees, respectively. The second (N or S) and fourth token (E or W) specify to which hemisphere the point belongs. The values of lat and long satisfy 0 ≤ lat ≤ 90 and 0 ≤ long ≤ 180.

In each coordinate representation, you may assume that p1 and p2 never coincide, and the line segment p1-p2 is not the diameter of the unit sphere. You may also assume that values of lat and long in the input are integers. It is guaranteed that there are two intersections if there are any intersections.


For each test case, output a line gCase n:h, where n is the test case number. After the line, output gNo intersec- tion.h if two circles never intersect. Otherwise, output the coordinates of intersections with the same format as input. The values should be printed with three digits after the decimal point. If the coordinates can be represented in several ways, any of them suffice. All values should be printed without negative signs.

Output a blank line between each test case.

Sample Input

30 N 50 E
30 N 130 W
0 N 90 E
0 N 30 W
45 N 180 E
45 N 0 W
40 N 10 W
40 S 10 W

Output for the Sample Input

Case 1:
30.000 N 84.736 E
30.000 N 24.736 W

Case 2:
No intersection.

Source: ACM-ICPC Japan Alumni Group Practice Contest , for World Finals, Tokyo, Japan, 2008-02-24