Manors

Some famous theoretical scientists with their wives bought $4095^2$ acres of Prairie Nebraska. They describe it as a square of length $4095$. Now they want to build their private manors. Each theoretical scientist with his wife (for example, the $i$-th couple) select $m$ fixed positions in the square, denoted by $(x_{i1},y_{i1}),(x_{i2},y_{i2}),\cdots,(x_{im},y_{im})$, to put their own flags. We have known that the gravity centres of flags for two different theoretical scientists are distinct.

For every inch of land in this square, the influence of the $i$-th theoretical scientists and his wife, denoted by $I_i((x,y))$, is defined as
$$I_i((x,y)) = \{\frac{1}{m} \sum_{j=1}^m ((x-x_{ij})^2 + (y-y_{ij})^2)\}^{-1}.$$
The couple with the highest influence has the ownership. Your mission is to compute the areas of each private manors.

The input contains several test cases. The first line of the input is a single integer $t~(t\le 10)$ which is the number of test cases. Then $t$ test cases follow.

Each test case contains several lines. The first line contains the integer $n~(1\le n\le 100)$ which is the number of theoretical scientists, and the integer $m~(1\le m\le 2000)$. The $i$-th line of the next $n$ lines contains $2m$ integers $x_1,y_1,x_2,y_2,\cdots,x_m,y_m$ between $0$ to $4095$ which correspond to the positions of $m$ flags belonging to the $i$-th theoretical scientist and his wife.

For each test case, you should output the areas of each manors in one line.

You need to do decimals to round up and round down numbers (omitting decimal fractions smaller than $0.5$ and counting all others, including $0.5$, as $1$).

2

4 1
1 1
1 3
3 1
3 3

2 2
1 1 1 3
2 1 3 2

Case #1: 4 8186 8186 16752649
Case #2: 2798933 13970093

2015 ACM/ICPC Asia Regional Shenyang Online