Chef and Employment Test Solution

Problem

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 (co-chefs 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 A1, A2, ..., AN, 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 A1, A2, ..., AN 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 ≤ Ai ≤ 1000.
• N + K is guaranteed to be odd.

 

Sample 1:

Input

Output

3
2 1
4 7
4 3
9 2 8 6
5 2
6 1 1 1 1

7
9
1

Explanation:

Test case $1$: A possible solution is to add element $9$ to the array. On sorting, the array becomes $[4, 7, 9]$. The element positioned at the center, after sorting, is $7$. It can be shown that the median of the array after inserting $1$ element cannot exceed $7$.

Test case $2$: A possible solution is to add elements $10, 20,$ and $30$ to the array. On sorting, the array becomes $[2, 6, 8, 9, 10, 20, 30]$. The element positioned at the center, after sorting, is $9$. It can be shown that the median of the array after inserting $3$ elements cannot exceed $9$.

Test case $3$: A possible solution is to add elements $2$ and $3$ to the array. On sorting, the array becomes $[1,1,1,1,2,3,6]$. The element positioned at the center, after sorting, is $1$. It can be shown that the median of the array after inserting $2$ elements cannot exceed $1$.

Program :

 #include <stdio.h>

void sort(int a[], int n);

int main() {

// your code goes here

int t,n,k,i,g;

scanf("%d",&t);

while(t--)

{

    scanf("%d%d",&n,&k);

   // scanf("%d",&k);

    int a[n];

    for(i=0;i<n;i++)

    {

        scanf("%d",&a[i]);

    }

    sort(a,n);

    g=(n+k)/2;

    printf("%d\n",a[g]);

}

return 0;

}

void sort (int a[] , int n)

{

    int temp,i,j;

    for(i=0;i<n;i++)

    {

        for(j=0;j<n-i-1; j++)

        {

            if(a[j]>a[j+1])

            {

                temp=a[j];

                a[j]=a[j+1];

                a[j+1]=temp;

            }

        }

    }

}