Problem D: LowbieH's best friend

Problem D: LowbieH's best friend

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1002  Solved: 250
[Submit][Status][Web Board]

Description

Skylar is LowbieH's best friend, so every day LowbieH gives Skylar a gift. Specifically, LowbieH will give Skylar a gift of value \(v_i\) in day i. Now Skylar wants to know the median of gift values on the odd days, specifically, on the first day, and the third day, the fifth day ... Can you help her to solve it?


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, represeenting the gift values \(v_1\), ... ,\(v_n\)( 1 <= n <= 300000, 0 <= \(v_i\) <= 300000)

Output

For each test case, output the median gift values every odd days.

Sample Input

1
5
1 2 3 4 5

Sample Output

1 2 3

HINT

[Submit][Status]