Convex Hull

Problem Description

There are n points in three dimensional space. Consider the convex hull of n points. Given a plane, you should work out the area of section of convex hull by the plane.

Input

First line contains T(T <= 10), a number of test cases. For each test case, there are two integer n and m, number of points and number of queries. Next n lines contains three integers x, y, z, coordinate of point. Next m lines contains four integers a, b, c, d, specifying the equation of plane: ax + by + cz + d = 0. 1 <= n <= 1000 1 <= q <= 1000 Absolute values of x, y, z, a, b, c and d are not greater than 2000.

Output

For each test case, first line contains “Case #x:”, x is the number of the case. For each query, you should print one float number in three decimal places in one line.

Sample Input

1
6 1
0 0 1
1 0 1
0 1 1
0 0 -1
1 0 -1
0 1 -1
0 0 1 0

Sample Output

Case #1:
0.500

Author

金策工业综合大学（DPRK）

Source

2016 Multi-University Training Contest 9