First, read the first half of the editorial.

Even if you spend \(O(|X|+|Y|)\) time to compare strings \(X\) and \(Y\), if each element is referenced at most \(O(\log N)\) time per step, and the sort finishes in \(O(\log N)\) recursive steps, the entire sort can be finished in \(O(\Sigma |S_i| \log^2 N)\) time.

Such a sort can be achieved by combining merge sort and exponential search.
Specifically, the following procedure achieves the objective:

• Just as the merge sort, divide the array into two halves \(A\) and \(B\), and sort each of them individually.
• Then, we will merge \(A\) and \(B\). Repeat the following until the merge finishes:
  • The two arrays alternatively become the “kick array.” Let \(X\) be the kick array, and \(Y\) be the other.
  • The objective here is to finish sorting up to the position where the first element of \(X\) ends up. Here, perform an exponential search to determine how many elements of among \(Y\) should be inserted before that.
    • As the first phase of the exponential search, compare the first element of \(X\) with the \(2^k\)-th term of \(Y\), for \(k=0,1,\dots\).
    • This identifies \(k\) such that the first element of \(X\) is inserted between the \(2^{k-1}\)-th and \(2^k\)-th element of \(Y\). As the second phase of the exponential search, binary search for the actual position.
    • As a result, we complete sorting the elements up to the position where the first element of \(X\) ends up.

For details, see also the sample code.

This way, each element is guaranteed to referenced at most \(O(\log N)\) time during a single recursion step. The proof follows.

• An element in \(X\) is referenced \(O(\log N)\) time as the first element of \(X\).
• We will consider how any times an element in \(Y\) is referenced.
  
  • During the first phase of the binary search, an element is referenced at most once as the \(2^k\)-th element, for each \(k\).
    • This is because the “kick array” is picked alternately, and thus for the next time this array is referenced as \(Y\), the position of the \(2^k\)-th element is always advanced.
    • Regarding that we have sorted the first \(2^{k-1}\) elements of \(Y\) before entering the second phase of the exponential search, by the same reason, each element is referenced at most once as the \(2^k\)-th element for each \(k\).

Hence, we assert that every element is referenced at most \(O(\log N)\) time in all cases, thus concluding the proof.

This way, the problem has been solved in a total of \(O(\Sigma |S_i| \log^2 N)\) time.

This sort algorithm utilizes the idea of Timsort, which involves a similar process.
In environments like CPython or OpenJDK, where the standard sorting algorithm employs Timsort, you may pass a comparison function that costs \(O(|X|+|Y|)\) time to compare strings \(|X|\) and \(|Y|\) without worrying so much about the time complexity and still get AC (accepted).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

template <class RandomAccessIterator, class Compare> constexpr void exponential_merge_sort(
  RandomAccessIterator first, RandomAccessIterator last, Compare comp){
  auto len=(last-first);
  if(len<=1){return;}

  auto mid=first+len/2;
  exponential_merge_sort(first,mid,comp);
  exponential_merge_sort(mid,last,comp);

  auto a=vector(first,mid);
  auto b=vector(mid,last);
  auto ai=a.begin();
  auto bi=b.begin();
  bool side=false;
  while(ai!=a.end() || bi!=b.end()){
    if(ai==a.end()){
      while(bi!=b.end()){
        (*first)=(*bi);
        first++; bi++;
      }
      break;
    }
    else if(bi==b.end()){
      while(ai!=a.end()){
        (*first)=(*ai);
        first++; ai++;
      }
      break;
    }
    side=(!side);
    if(side){
      // kick a.begin();
      long long d=1;
      while(true){
        auto it=ranges::next(bi,d-1,b.end());
        if(it==b.end()){break;}
        if(comp((*it),(*ai))){d<<=1;}
        else{break;}
      }
      d>>=1;
      long long c=d;
      while(d>=2){
        d>>=1;
        auto it=ranges::next(bi,c+d-1,b.end());
        if(it==b.end()){continue;}
        if(comp((*it),(*ai))){c+=d;}
      }
      while(c--){
        (*first)=(*bi);
        first++; bi++;
      }
      (*first)=(*ai);
      first++; ai++;
    }
    else{
      // kick b.begin();
      long long d=1;
      while(true){
        auto it=ranges::next(ai,d-1,a.end());
        if(it==a.end()){break;}
        if(comp((*it),(*bi))){d<<=1;}
        else{break;}
      }
      d>>=1;
      long long c=d;
      while(d>=2){
        d>>=1;
        auto it=ranges::next(ai,c+d-1,a.end());
        if(it==a.end()){continue;}
        if(comp((*it),(*bi))){c+=d;}
      }
      while(c--){
        (*first)=(*ai);
        first++; ai++;
      }
      (*first)=(*bi);
      first++; bi++;
    }
  }
}

bool comp(const string &x,const string &y){
  return (x+y < y+x);
}

string concat(vector<string> &s){
  string res="";
  for(auto &nx : s){ res+=nx; }
  return res;
}

int main(){
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<string> s(n);
    for(auto &nx : s){cin >> nx;}
    exponential_merge_sort(s.begin(),s.end(),comp);

    if(n==2){
      cout << s[1]+s[0] << "\n";
      continue;
    }
    
    bool ok=false;
    for(int i=1;i<n;i++){
      if(s[i-1]+s[i] == s[i]+s[i-1]){ok=true; break;}
    }
    if(ok){
      cout << concat(s) << "\n";
      continue;
    }

    swap(s[n-1],s[n-2]);
    string c1=concat(s);
    swap(s[n-1],s[n-2]);
    swap(s[n-2],s[n-3]);
    cout << min(c1,concat(s)) << "\n";
  }
  return 0;
}