Chef and Employment Test

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Even though it was a little unexpected, Chef did it! He has finally opened a new restaurant!
As you all know, to make everything go well, Chef needs employees (cochefs if you might say). Because Chef is a perfectionist, he planned to employ only chefs who are good at competitive progeamming. Hence, Chef asked for help from his friends Shahhoud and Said. Knowing that many people (such as Ahmad, Nour, Majd and Joud) will apply for the job, they decided to choose only the best appliers.
As the day of the employment came, people lined up in front of the restaurant applying for the job. Before accepting any appliers, Shahhoud and Said decided to make them answer a simple question, in order to determine which of them better deserves the job.
Given an array of N elements A_{1}, A_{2}, ..., A_{N}, each applier was asked to insert any K integers he wants to this array. Eventually, each applier will be asked to write down the median among all the elements in his resulting array. Many appliers asked for your help to determine what is the greatest median they can get after inserting any K elements they want?
Note that the median in an array is the element positioned at the center of the array after sorting it. E.g. the median in [2, 1, 5, 2, 4] is 2, and the median in [3, 3, 1, 3, 3] is 3.
Input
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space separated integers N and K denoting the array length, and the number of elements to be inserted.
The second line of each test case contains N space separated integers A_{1}, A_{2}, ..., A_{N} denoting the elements of the array.
Output
For each test case output a single line, containing a single integer, indicating the greatest median the applier can obtain after inserting exactly K new elements into the given array.
Constraints
 1 ≤ T ≤ 100.
 0 ≤ K < N ≤ 100.
 0 ≤ A_{i} ≤ 1000.
 N + K is guaranteed to be odd.
Example
Input: 3 2 1 4 7 4 3 9 2 8 6 5 2 6 1 1 1 1 Output: 7 9 1
Explanation
Example case 1. One of the possible solutions is to add 9 making the array [4, 7, 9], whose median is 7
Example case 3. No matter what elements you add to this array, the median will always be 1
Author:  saeed_sryhini 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/CK87MEDI 
Tags  cakewalk, cook87, median, saeed_sryhini, sorting 
Date Added:  19102017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 