1362 - Distance

Time Limit: 10s Memory Limit: 256MB

Submissions: 58 Solved: 4
Description
The furthest distance in the world is not between life and death But when i stand in front of you , Yet you don't know that I love you The furthest distance in the world is not when i stand in front of you, Yet you can't see my love But when undoubtedly knowing the love from both, Yet cannot be together The furthest distance in the world is not being apart while being in love But when plainly can not resist the yearning, Yet pretending you have never been in my heart The furthest distance in the world is not when plainly can not resist the yearning, yet pretending you have never been in my heart But using one's indifferent heart to dig an uncrossable river for the one who loves you
                            Tagore——Stray Birds
As a status shared by ACMer on RenRen says: It’s a signal to be love, when a girl becomes an ACMer. It’s a signal to be lonely, when a boy becomes an ACMer. Taney, The leader of CUG ACM team, is anxious about this problem for the team members. He wants to help every male member to find a girlfriend. To finish this important and hard task, he designs a metric, to measure the personality differences between boys and girls. According to Taney’s theory, the personality differences between lovers should not be too much or too less. Too much means the two one are not live together well, and too less means the two one are too similarly to find funny to live together. The personality differences are measured by a distance. Everyone has a vector (A, B, C) to describe his personality. And the distance between a boy and a girl is the Euclidean distance:
There are N girls in Taney’s girl Database, give you a boy’s personality please find out the Kth closest girl to him.
Input
The first line of the input gives the number of test cases, T(T≦10). The first line of each case contains two integers, N and M(N, M≦20000). N is the number of girls, M is the number of boys. N+M lines follow, the first N lines gives out the personality vector of the N girls, and the last M lines,we first give out the K(K≦100), which means he want find the Kth closest girl, then the personality vector of the M boys, for each boy.
Output
For each boy output the distance between him and the Kth closest girl. Round the numbers in the output to 6 digits after decimal point.
Sample Input
1
5 5
4.5  1.0  9.5 
3.0  7.0  5.0 
0.0  8.0  0.5 
6.0  0.0  9.5 
5.5  3.0  7.5 
3  2.0  0.0  7.0 
3  4.0  0.5  6.0 
3  8.0  3.0  6.5 
3  4.5  6.5  8.0 
3  1.5  7.0  0.0 
Sample Output
4.716991
4.062019
5.024938
5.700877
9.394147
Hint
Source
中国地质大学(武汉)第七届ACM程序设计大赛暨华中地区部属高校ACM邀请赛