Operation: Merchant Boorinei

Little girls and boys on vessels deserve a spooky Christmas too! But delivering presents to moving targets is a real hassle: you must fly your coffin-sleigh to where a vessel will be, not where it is now. The Pumpking King has asked you to write a program that, given a set of vessels, plans a route that completes every delivery in the minimum amount of time.

You are given the initial coordinates of the sleigh and of each vessel carrying children. Each vessel travels constantly at the heading and speed given by its velocity vector (vx, vy): after 1 hour it has moved vx km in the x direction and vy km in the y direction (vx and vy may be negative). The length of this vector is the vessel's speed. Jack's sleigh can fly at a constant speed in any direction (assume acceleration and deceleration are instantaneous). Jack must land on each vessel at least once, and unloading the presents takes 1 hour at each vessel. While unloading, Jack stays aboard the vessel, so he moves along with it. The sleigh carries enough presents for all the children, so it never needs to return to base partway. All coordinates are in km, and all velocities and speeds are in km/h.

Find the shortest time for Jack to deliver presents to every vessel and return to his starting location.

The input consists of several test cases. Each case starts with a line containing the integer N (1 <= N <= 8), the number of vessels. The next N lines each contain 4 space-separated integers: the initial (x, y) coordinates of the i-th vessel and its velocity vector (vx, vy). The last line of each case contains 3 integers: the initial (x, y) coordinates of the sleigh and the sleigh's speed. The end of input is indicated by a case that starts with N = 0, which must not be processed. Every input integer has absolute value at most 1000. You may assume the sleigh travels faster than every vessel. The vessels' paths may cross each other or even the sleigh's initial location, but the captains make minor course corrections to avoid collisions, so you do not need to account for this.

For each case, print its case number, a colon, and the minimum time needed to complete the delivery, in the format:

Case a: b hour(s) c minute(s) d second(s)

where a, b, c, and d are appropriate non-negative integers and c and d are at most 59. The time is rounded up to the next second.