10351035 SUSTech Online Judge
Problem 1035 --Find the Median

1035: Find the Median

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 304  Solved: 45
[Submit][Status][Web Board]

Description

Giving you N distinct numbers and inserting them into a list one by one. Now ItakEjgo wants to know the median of each odd step. The median is the middle number after sort the numbers.

Input

The first line will be an integer T(1 <= T <= 10), which is the number of test cases.

For each test case, the first will be an integer n. Then there will be n integers, a[i].

( 1 <= n <= 2000, 0 <= a[i] <= 10000)


Output

For each test case, output the median for each odd step in a line.

Sample Input

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

Sample Output

1 2 3
1 2 7 6

HINT

Hard problem

Source

[Submit][Status]