Problem: You're given a list of n strings a1, a2, ..., an. You'd like to concatenate them together in some order such that the resulting string would be lexicographically smallest.

Given the list of strings, output the lexicographically smallest concatenation.

Input

The first line contains integer n — the number of strings (1 ≤ n ≤ 5·104).

Each of the next n lines contains one string ai (1 ≤ |ai| ≤ 50) consisting of only lowercase English letters. The sum of string lengths will not exceed 5·104.

Output

Print the only string a — the lexicographically smallest string concatenation.

Examples

Input

4
abba
abacaba
bcd
er


Output

abacabaabbabcder


Input

5
x
xx
xxa
xxaa
xxaaa


Output

xxaaaxxaaxxaxxx


Input

3
c
cb
cba


Output

cbacbc

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.stream.*;

@SuppressWarnings("unchecked")
public class P632C {

  final static int SHIFT = 5;
  final static int MAXD = 50;
  final static BigInteger [] OR = new BigInteger [MAXD];
  static {
    OR[1] = BigInteger.valueOf((1 << SHIFT) - 1);
    for (int i = 2; i < MAXD; i++) {
      OR[i] = OR[i - 1].shiftLeft(SHIFT).or(OR[1]);
    }
  }

  class Word implements Comparable<Word> {
    BigInteger w = BigInteger.ZERO;
    String s;
    int len;

    public Word(String s) {
      this.s = s;
      len = s.length();

      for (int i = 0; i < s.length(); i++) {
        w = w.shiftLeft(SHIFT).or(BigInteger.valueOf(s.charAt(i) - 'a' + 1));
      }
    }

    @Override
    public int compareTo(Word aw) {
      BigInteger w1 = w;
      BigInteger w2 = aw.w;
      int d = len - aw.len;

      if (d < 0) {
        w1 = w1.shiftLeft(SHIFT * (-d)).or(OR[-d]);
      } else if (d > 0) {
        w2 = w2.shiftLeft(SHIFT * (+d)).or(OR[+d]);
      }

      return w1.compareTo(w2);
    }

    public int concatCmp(Word aw) {
      return w.shiftLeft(SHIFT * aw.len).or(aw.w).compareTo(aw.w.shiftLeft(SHIFT * len).or(w));
    }

    @Override
    public String toString() {
      return s;
    }
  }

  public void run() throws Exception {
    int n = nextInt();

    Word [] w = new Word [n];
    for (int i = 0; i < n; i++) {
      w[i] = new Word(next());
    }

    Arrays.sort(w);

    int si = 0;
    int fi = n - 1;
    boolean done = false;
    while (!done) {
      done = true;
      fi--;
      for (int i = si; i <= fi; i++) {
        if (w[i].concatCmp(w[i + 1]) > 0) {
          Word tw = w[i]; w[i] = w[i + 1]; w[i + 1] = tw;
          done = false;
        }
      }

      if (done) {
        break;
      }
    
      done = true;
      si++;
      for (int i = fi; i >= si; i--) {
        if (w[i].concatCmp(w[i - 1]) < 0) {
          Word tw = w[i]; w[i] = w[i - 1]; w[i - 1] = tw;
          done = false;
        }
      }
    }

    for (int i = 0; i < n; i++) {
      print(w[i]);
    }
  }

  public static void main(String... args) throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedOutputStream(System.out));
    new P632C().run();
    br.close();
    pw.close();
    System.err.println("\n[Time : " + (System.currentTimeMillis() - startTime) + " ms]");
  }

  static long startTime = System.currentTimeMillis();
  static BufferedReader br;
  static PrintWriter pw;
  StringTokenizer stok;

  String nextToken() throws IOException {
    while (stok == null || !stok.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null) { return null; }
      stok = new StringTokenizer(s);
    }
    return stok.nextToken();
  }

  void print(byte b) { print("" + b); }
  void print(int i) { print("" + i); }
  void print(long l) { print("" + l); }
  void print(double d) { print("" + d); }
  void print(char c) { print("" + c); }
  void print(Object o) {
    if (o instanceof int[]) { print(Arrays.toString((int [])o));
    } else if (o instanceof long[]) { print(Arrays.toString((long [])o));
    } else if (o instanceof char[]) { print(Arrays.toString((char [])o));
    } else if (o instanceof byte[]) { print(Arrays.toString((byte [])o));
    } else if (o instanceof short[]) { print(Arrays.toString((short [])o));
    } else if (o instanceof boolean[]) { print(Arrays.toString((boolean [])o));
    } else if (o instanceof float[]) { print(Arrays.toString((float [])o));
    } else if (o instanceof double[]) { print(Arrays.toString((double [])o));
    } else if (o instanceof Object[]) { print(Arrays.toString((Object [])o));
    } else { print("" + o); }
  }
  void print(String s) { pw.print(s); }
  void println() { println(""); }
  void println(byte b) { println("" + b); }
  void println(int i) { println("" + i); }
  void println(long l) { println("" + l); }
  void println(double d) { println("" + d); }
  void println(char c) { println("" + c); }
  void println(Object o) { print(o); println(); }
  void println(String s) { pw.println(s); }
  int nextInt() throws IOException { return Integer.parseInt(nextToken()); }
  long nextLong() throws IOException { return Long.parseLong(nextToken()); }
  double nextDouble() throws IOException { return Double.parseDouble(nextToken()); }
  char nextChar() throws IOException { return (char) (br.read()); }
  String next() throws IOException { return nextToken(); }
  String nextLine() throws IOException { return br.readLine(); }
  int [] readInt(int size) throws IOException {
    int [] array = new int [size];
    for (int i = 0; i < size; i++) { array[i] = nextInt(); }
    return array;
  }
  long [] readLong(int size) throws IOException {
    long [] array = new long [size];
    for (int i = 0; i < size; i++) { array[i] = nextLong(); }
    return array;
  }
  double [] readDouble(int size) throws IOException {
    double [] array = new double [size];
    for (int i = 0; i < size; i++) { array[i] = nextDouble(); }
    return array;
  }
  String [] readLines(int size) throws IOException {
    String [] array = new String [size];
    for (int i = 0; i < size; i++) { array[i] = nextLine(); }
    return array;
  }
}