Programming League 2004/05

The election campaign of the mayor of Byteland continues. His advisors firmly believe that a military touch might do good to his image. On the other hand, aggressive use of arms might arouse the insane anger of the pacifist part of the electorate. So, investing in national defence seems to be the best solution. And this is why the capital of Byteland will receive its first ever atomic shelters.

The Bytelandian capital consists of exactly n buildings and the mayor intends to build shelters underneath exactly k of them. Now it is your task to layout the shelters in the city in such a way as to minimise the maximum distance a citizen of Byteland may have to cover to reach the nearest atomic shelter. After all, there is nothing more important than a mayor who guarantees your safety by putting an atomic shelter not far from your house.

Input

t [the number of test cases <= 1000]
n k [2 <= the number of different buildings <= 100, 1 <= the number of shelters <= n-1]
x1 y1 [-1000 <= coordinates <= 1000]
x2 y2
.....
x_n y_n
[next test cases]

Output

case i Y [N if you wish to skip this test case]
b1 b2... b_k [numbers of buildings to put shelters in, in increasing input order]
[next test cases]

Scoring

The score awarded to your program is the sum of scores for individual test cases. For the i-th test case you will receive diam / dist points, where diam is the distance between the furthest two buildings of the city, while dist is the longest distance from a building to the nearest shelter in your solution. If you don't want to solve the i-th test case, you may output the line 'case i N' and nothing else.

Example

Input:
5
5 2
-3 -4
-4 3
2 -3
-2 -3
-5 5
5 4
2 0
-5 -4
1 -1
-1 0
5 -5
5 2
-3 0
5 -2
-1 -5
2 4
4 5
5 3
5 0
-1 -5
3 2
-5 1
-1 3
5 4
-1 2
1 1
5 4
0 5
-2 2

Output:
case 1 Y
3 4
case 2 Y
1 3 4 5
case 3 Y
4 5
case 4 Y
1 2 3
case 5 N

Score:
5.592004

Bonus info: If score = xxx.xxxaaa, aaa means the number of test cases with Y answer.