#include <bits/stdc++.h>
using namespace std;
static const int INTINF = (INT_MAX >> 1);
static const long long LLINF = (LLONG_MAX >> 1);
static const int MAX = 1e5 + 1;
static const long long MOD = 1e9 + 7;
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N>
string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U>
string to_string(pair<T, U> p);
template <class C>
string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U>
string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
int main(int argc, const char* argv[]) {
  std::cout << std::fixed << std::setprecision(15);
  int T;
  cin >> T;
  for (int _ = 0; _ < (T); ++_) {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < (N); ++i) cin >> a[i];
    sort((a).begin(), (a).end());
    vector<int> ans;
    int k = 0;
    for (int i = 0; i < (N); ++i) {
      if (k % 2 == 0) {
        ans.push_back(a[a.size() - 1]);
        a.erase(a.end() - 1);
      } else {
        ans.push_back(a[0]);
        a.erase(a.begin());
      }
      k++;
    }
    reverse((ans).begin(), (ans).end());
    for (int i = 0; i < (N); ++i) {
      if (i) cout << " ";
      cout << ans[i];
    }
    cout << endl;
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

You have array of n numbers a_{1}, a_{2}, …, a_{n}. 

Rearrange these numbers to satisfy |a_{1} - a_{2}| ≤ |a_{2} - a_{3}| ≤ … ≤ |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 ≤ t ≤ 10^{4}) — the number of test cases.

The first line of each test case contains single integer n (3 ≤ n ≤ 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}, …, a_{n} (-10^{9} ≤ a_{i} ≤ 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 ≤ |a_{2} - a_{3}| = 1 ≤ |a_{3} - a_{4}| = 2 ≤ |a_{4} - a_{5}| = 2 ≤ |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 ≤ |a_{2} - a_{3}| = 2 ≤ |a_{3} - a_{4}| = 4. There are other possible answers like "2 4 8 1".

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
static const int INTINF = (INT_MAX >> 1);
static const long long LLINF = (LLONG_MAX >> 1);
static const int MAX = 1e5 + 1;
static const long long MOD = 1e9 + 7;
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N>
string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U>
string to_string(pair<T, U> p);
template <class C>
string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U>
string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
int main(int argc, const char* argv[]) {
  std::cout << std::fixed << std::setprecision(15);
  int T;
  cin >> T;
  for (int _ = 0; _ < (T); ++_) {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < (N); ++i) cin >> a[i];
    sort((a).begin(), (a).end());
    vector<int> ans;
    int k = 0;
    for (int i = 0; i < (N); ++i) {
      if (k % 2 == 0) {
        ans.push_back(a[a.size() - 1]);
        a.erase(a.end() - 1);
      } else {
        ans.push_back(a[0]);
        a.erase(a.begin());
      }
      k++;
    }
    reverse((ans).begin(), (ans).end());
    for (int i = 0; i < (N); ++i) {
      if (i) cout << " ";
      cout << ans[i];
    }
    cout << endl;
  }
  return 0;
}

```