<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

347. Join the Strings
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



His Royal Highness King of Berland Berl XV was a very wise man and had a very accomplished wife, who was aware of the fact, that prominent and outstanding personalities once having written down their names on the pages of glorious History, remain there forever. His Royal Highness King Berl XV experienced an intrinsic, lost nowadays, deep and sincere sense of respect and trust for his beloved spouse. So he decided to acquire a chronicler of his own. Due to the ambiguous nature of misunderstanding and the crying injustice of history to ambiguity, he decided to leave all his royal responsibilities aside and made up his royal mind to find the chronicler, who will make him famous, depicting all his heroic deeds truthfully and gloriously enough.

The King assembled the greatest minds of his kingdom at the Academic Chroniclers Meeting (ACM), as he named it, and decided to test their might. The task was to build the Smallest Lexicographical Concatenation (SLC) out of the given N strings. SLC of N strings s1,..., sN is the lexicographically smallest their concatenation si1 +... + siN, where i1,..., iN is a permutation of integers from 1 through N. It's a great privilege to be a chronicler, so don't miss your chance and don't screw it up! Make the king choose you!

Input
The first line of the input file contains a single integer N (1 ≤ N ≤ 100) indicating the number of strings. The following N lines contain N strings, one string per line. The length of each string is no more than 100 characters. Each string consists only of lowercase Latin letters. There are no any leading or trailing spaces.

Output
Print the SLC of the given N strings to the output file as a single line.

Example(s)
sample input
sample output
6
it
looks
like
an
easy
problem
aneasyitlikelooksproblem

<|response|>
1. Abridged Problem Statement  
Given N (1 ≤ N ≤ 100) lowercase strings (each of length ≤ 100), find a permutation of them whose concatenation is lexicographically smallest, and print that smallest concatenation.

2. Key Observations  
- When deciding whether string a should come before string b, you only need to compare the two possible concatenations:  
  • a + b  
  • b + a  
  whichever is lexicographically smaller indicates the correct order between a and b.  
- By sorting all N strings with this pairwise comparator, you guarantee the global concatenation is the lexicographically smallest possible.  
- Sorting with a custom comparator based on (a+b) < (b+a) takes O(N log N) comparisons, each comparison costs up to O(L) time for strings of length L (here L ≤ 100), which easily fits within the problem limits.

3. Full Solution Approach  
1. Read integer N.  
2. Read the N strings into a list (or array).  
3. Define a comparator such that for two strings x and y,  
     x comes before y if and only if x+y < y+x lexicographically.  
4. Sort all strings using this comparator.  
5. Concatenate the sorted strings in order and print the result.  

Proof Sketch of Correctness  
If in an optimal solution b is placed before a but a+b < b+a, swapping them makes the overall concatenation lexicographically smaller—contradicting the optimality. Therefore, no such inversion can exist, and the greedy sort is correct.

Complexity  
- Sorting cost: O(N log N) comparisons  
- Each comparison cost: O(L) where L ≤ 100  
- Total: O(N L log N) ≈ O(100·100·log 100) ≪ time limit  

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// Comparator: returns true if a should go before b
// i.e., if concatenating a then b is lexicographically smaller
// than b then a.
bool lexConcatCompare(const string &a, const string &b) {
    return a + b < b + a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];  // each string is lowercase letters, no spaces
    }

    // Sort using the custom comparator
    sort(S.begin(), S.end(), lexConcatCompare);

    // Output the concatenation of all strings in sorted order
    for (const string &str : S) {
        cout << str;
    }
    cout << "\n";

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
from functools import cmp_to_key

def compare(a, b):
    """
    Comparator for sorting:
    Return negative if a should come before b,
    i.e., if a+b < b+a.
    """
    if a + b < b + a:
        return -1
    elif a + b > b + a:
        return 1
    else:
        return 0

def main():
    data = sys.stdin.read().split()
    # First token is N, then come the N strings
    n = int(data[0])
    strings = data[1:]  # list of length n

    # Sort with our custom comparator turned into a key
    strings.sort(key=cmp_to_key(compare))

    # Join and print the result
    result = ''.join(strings)
    sys.stdout.write(result)

if __name__ == "__main__":
    main()
```