You have array of $n$ numbers $a_{1}, a_{2}, \ldots, a_{n}$. 

Rearrange these numbers to satisfy $|a_{1} - a_{2}| \le |a_{2} - a_{3}| \le \ldots \le |a_{n-1} - a_{n}|$, where $|x|$ denotes absolute value of $x$. It's always possible to find such rearrangement.

Note that all numbers in $a$ are not necessarily different. In other words, some numbers of $a$ may be same.

You have to answer independent $t$ test cases.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases.

The first line of each test case contains single integer $n$ ($3 \le n \le 10^{5}$) — the length of array $a$. It is guaranteed that the sum of values of $n$ over all test cases in the input does not exceed $10^{5}$.

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($-10^{9} \le a_{i} \le 10^{9}$).


-----Output-----

For each test case, print the rearranged version of array $a$ which satisfies given condition. If there are multiple valid rearrangements, print any of them.


-----Example-----
Input
2
6
5 -2 4 8 6 5
4
8 1 4 2

Output
5 5 4 6 8 -2
1 2 4 8



-----Note-----

In the first test case, after given rearrangement, $|a_{1} - a_{2}| = 0 \le |a_{2} - a_{3}| = 1 \le |a_{3} - a_{4}| = 2 \le |a_{4} - a_{5}| = 2 \le |a_{5} - a_{6}| = 10$. There are other possible answers like "5 4 5 6 -2 8".

In the second test case, after given rearrangement, $|a_{1} - a_{2}| = 1 \le |a_{2} - a_{3}| = 2 \le |a_{3} - a_{4}| = 4$. There are other possible answers like "2 4 8 1".

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for yguagwu in range(t):
    n = int(input())
    a = sorted(list(map(int,input().split())))
    b = []
    for i in range(n):
        if i % 2 == 0:
            b.append(a[(-i//2-1)])
        else:
            b.append(a[i//2])
    print(*b[::-1])


import sys
input = sys.stdin.readline

Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    A = list(map(int, input().split()))
    Query.append((N, A))

for N, A in Query:
    A.sort()
    l = 0
    r = N-1
    ans = []
    for i in range(N):
        if i%2 == 0:
            ans.append(str(A[l]))
            l += 1
        else:
            ans.append(str(A[r]))
            r -= 1
    print(" ".join(ans[::-1]))

t=int(input())


for _ in range(t):
    valid=True
    n=int(input())
    ar=[int(x) for x in input().split()]
    ar=sorted(ar)
    res=[]
    ar1=ar[:n//2]
    ar2=ar[n//2:][::-1]
    for a,b in zip(ar1,ar2):
        res.append(a)
        res.append(b)
    if len(ar2)>len(ar1):
        res.append(ar2[-1])

    for v in res[::-1]:
        print(v,end=" ")
    print()


t = int(input())
for q in range(0, t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    b = []
    for i in range(0, n // 2):
        b.append(a[i])
        b.append(a[n - i - 1])
    if n % 2 != 0:
        b.append(a[n // 2])
    b.reverse()
    print(*b)


'''from collections import Counter,defaultdict,deque

from math import factorial as fact
import math'''

#total=0
t = int(input())

#n,m,k = [int(x) for x in input().split()]
#d = [int(x) for x in input().split()]
for i in range(t):
    n = int(input())
    arr = [int(x) for x in input().split()]
    arr.sort()
    ans = []
    ans.append(arr[0])
    p1 = 1
    p2 = n-1
    while p2>=p1:
        if abs(ans[-1]-arr[p1])>abs(ans[-1]-arr[p2]):
            ans.append(arr[p1])
            p1+=1
        else:
            ans.append(arr[p2])
            p2-=1
    ans.reverse()
    print(*ans)



for f in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    b=[0]*n
    i=n-1
    big=0
    foo=0
    while i>=0:
        if big==1:
            b[i]=a[-foo]
            big=0
        else:
            b[i]=a[foo]
            foo+=1
            big=1
        i-=1
    print(*b)

def main():
	t = int(input())
	for tt in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		l.sort()
		t = []
		if n % 2:
			t.append(l[n // 2])
		for i in range(n // 2):
			t.append(l[n // 2 - i - 1])
			t.append(l[(n + 1) // 2 + i])
		print(*t)
main()

import math
import sys
input = sys.stdin.readline

t=int(input())
for i in range(t):
	n=int(input())
	arr=list(map(int,input().split()))
	arr.sort()
	ans=[]
	cur=n//2
	if n%2==0:
		flag=True
	else:
		flag=False
	for i in range(n):
		if flag==True:
			ans.append(arr[cur])
			cur-=(i+1)
			flag=False
		else:
			ans.append(arr[cur])
			cur+=(i+1)
			flag=True

	print(*ans)


import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())
for t in range(T):
    n = int(lines[2*t+1].strip())
    nums = list(map(int, lines[2*t+2].strip().split(" ")))
    nums.sort()
    res = [0 for _ in range(n)]
    res[0] = nums[0]
    for i in range(n):
        if i % 2 == 0: res[i] = nums[i//2]
        else: res[i] = nums[-(i+1)//2]
    print(" ".join(map(str, res[::-1])))

from sys import stdin
input=stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    a=sorted(list(map(int,input().split())))
    b=[0]*n
    j=0
    while j < n:
        if j % 2 == 0: b[j] = a[j//2]
        else: b[j] = a[n - 1 - j//2]
        j+=1
    print(*b[::-1])    


t = int(input())

for _ in range(t):
    n = int(input())
    As = list(map(int, input().split()))
    As.sort()
    left = 0
    right = n-1
    res = []
    while left <= right:
        if left == right:
            res.append(As[left])
            break
        res.append(As[right])
        res.append(As[left])
        right -= 1
        left += 1
    print(" ".join(map(str, res[::-1])))


t = int(input())

for _ in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    s = 0
    e = n - 1
    l2 = []
    c = True
    while s <= e:
        if c:
            l2.append(l[s])
            s += 1
        else:
            l2.append(l[e])
            e -= 1
        c = not c
    print(" ".join(map(str, l2[::-1])))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	if n % 2 == 0:
		l, r = n // 2 -1, n //2
	else:
		print(a[n//2], end=" ")
		l, r = n // 2 -1, n //2 + 1

	while l > -1 and r < n:
		print(a[l], a[r], end = " ")
		l -= 1
		r += 1
	print()