Description
Consider a rectangular grid paper with width W units and height H units. We mark some points on the paper, and wrap it around with the left and the right edges glued together to form a cylinder of height H and circumference W.
Find a rectangle R of smallest area, whose four vertices fall on the grid points, that contains all the points we marked. Note that the interior of the rectangle could now cross the edges on the left and the right, since we have wrapped the paper around. For example, the figure below illustrates a valid rectangle with its lower-left corner and upper-right corner locating at (24, 2) and (6, 6) on a grid paper of width 28 units and height 9 units. The bold black line is the glued left edge and right edge of the grid paper.
Figure. An example of a valid rectangle with its interior cross the left and the right edge of the grid paper
Input
The first line of the input contains an integer T, denoting the number of test cases. Each case starts with three integers N, W, H, which are the number of points marked, the width and the height of the grid paper. Each of the following N lines contains a pair of integers x (0 ≤ x ≤ W), y (0 ≤ y ≤ H), representing the x, y coordinates of the point. There will be a blank line before the first line of each case. You may assume that there is no degenerated case that all of the points lie on a line parallelling to the x-axis or y-axis.
Output
For each test case, print the answer in the format “Case i: w h” in a line, where i is the sequence number of the test case, w (0 < w < W) and h (0 < h < H) are the width and the height of the minimum area rectangle R.
Technical Specification
For data set #1, N ≤ 5, W ≤ 500, H ≤ 250.
For data set #2, N ≤ 100, W ≤ 1000, H ≤ 500.
For data set #3, N ≤ 1000, W ≤ 30000, H ≤ 20000.
For data set #4, N ≤ 5000, W ≤ 5000000, H ≤ 3000000.