Filthy room P89133

Professor Filthy Frank has bought a new pet (whose name must remain undisclosed). He wants to prevent it from the horrible fate suffered by his previous hamster Stuart (which didn’t quite differ from that of his previous six pets). In particular, he wants to avoid using his sock to protect it from the cold. Can you find the warmest spot for Frank’s new pet?

Consider a bidimensional infinite world, where the temperature is given by the formula T(x,y) = px + qy + r. Frank’s room is an n-sided polygon determined by the intersection of n ‍half-planes, each one defined by the equation a_i x + b_i y + c_i ≥ 0.

Input

Input consist of several cases, each one with n, p, q and r, followed by n triples a_i b_i c_i defining the half-planes in any order. (For instance, below you can see the green room of the first sample case.) Assume 3 ≤ n ≤ 5000, that at least a_i or b_i is non-zero, and that the resulting room has indeed n sides.

Output

Print the highest temperature inside each room with three digits after the decimal point. The input cases do not have precision issues.

Observation

The expected solution has cost better than Θ(n²).