Skylar is LowbieH's best friend, so every day LowbieH gives Skylar a gift. There are totally \(n\) days. LowbieH will give Skylar a gift of value \(v_i\) on day \(i\) (\(i = 1, 2, \dots, n\)). 

On odd days (\(i \mod 2 = 1\)), Skylar will celebrate, inspect the gifts, and wonder the median of values of all gifts received. Can you help her to solve it?

Formally, for \(k = 1, 3, \dots, 2 \lfloor \frac {n+1}{2} \rfloor - 1\), please print out the median of \(v_1, v_2, \dots, v_k\).

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)