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.
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 K kids.
T <= 30
1 <= K <= N <= 20000
1 <= height <= 1000000000
T <= 30
1 <= K <= N <= 20000
1 <= height <= 1000000000
3 3 1 2 5 4 3 2 5 2 4 3 3 2 5 4
0 1 3
Migrated from old NTUJ.
Regional Amritapuri 2010
| No. | Testdata Range | Score |
|---|