AMR10G  Christmas Play
My kid's kindergarten class is putting up a Christmas play. (I hope he gets the lead role.) The kids are all excited, but the teacher has a lot of work. She has to produce costumes for a scene with K soldiers. She wants to buy all the costumes in the same size, allowing for some small amount of length alteration to be done by the kids' parents later. So she has taken all the kids' height measurements. Can you help her select K kids from her class of N to play the soldier role, such that the height difference between the tallest and shortest in the group is minimized, and alternations will be easiest? Tell her what this minimum difference is.
INPUT
The first line contains the number of test cases T. T test cases follow each containing 2 lines.
The first line of each test case contains 2 integers N and K.
The second line contains N integers denoting the height of the N kids.
OUTPUT
Output T lines, each line containing the required answer for the corresponding test case.
CONSTRAINTS
T <= 30
1 <= K <= N <= 20000
1 <= height <= 1000000000
SAMPLE INPUT
3 3 1 2 5 4 3 2 5 2 4 3 3 2 5 4SAMPLE OUTPUT
0 1 3EXPLANATION
In the first test case, the teacher needs to only select 1 kid and hence she can choose any kid since the height difference is going to be 0.
In the second test case, the teacher can choose kids with height 4 and 5.
In the third test case, the teacher is forced to choose all 3 kids and hence the answer = 52 = 3
hide comments
RAJAT SINGH:
20140315 20:28:46
Very easy problem got AC in second time...... 

Amit garg:
20140117 09:16:53
running program correctly on ideone but showing comile error here Last edit: 20140117 09:17:30 

Rudradeep Mukherjee:
20130712 06:14:16
Don't know what happened. Submitted the same code again and it got AC. :) Last edit: 20130712 06:18:52 

Hasil Sharma:
20130707 19:53:08
O(nlogn+n) !! indeed 

Rana Saha:
20130704 21:45:01
cakewalk! 

Centurion:
20130611 11:31:04
can anyone explain this test case and what will be the answer for it?


Aswin Murugesh:
20130521 15:24:36
I am getting WA but the given test cases are giving correct answers. Any tricky test cases?


Shubham Sharma:
20130314 20:59:14
very easy 

***:
20130307 17:02:36
plzz give some more test cases 

Secret:
20120821 11:59:33
my code is accepted in O(nlogn+n).no need to I/O optimization ... 
Added by:  Varun Jalan 
Date:  20101213 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ICPC Asia regionals, Amritapuri 2010 