Sakurako and Old Dictionary#11716
Sakurako is tidying the room. He has found a dictionary which contains strings. However, that dictionary is peculiar, and the presence of a string in the dictionary does not mean that such a word exists in reality.
Any word from Sakurako's world may be obtained by reordering the strings in the dictionary and concatenating them into one word. For example, if the dictionary contains the strings: \texttt{``a''},~\texttt{``b''},~\texttt{``ab''}, the possible words are: \texttt{``abab''},~\texttt{``aabb''},~\texttt{``baab''},~\texttt{``baba''},~\texttt{``abba''}.
As the dictionary is a bit out of date, new words have appeared in the world. They can still be obtained from that dictionary if at most strings are reversed.
Help Sakurako find the lexicographically smallest possible word in modern life.
The first line contains two integers n, k ~(1\le n\le 2\cdot 10^5;~k\in\{0,1\}) — the number of words in the dictionary and the number of possible reversals.
Each of the following lines contains a string s~(1\le |s_i|\le 2\cdot 10^5) which belongs to the dictionary.
It is guaranteed that \sum |s_i|\le 4\cdot 10^5 and all the strings consist of lowercase English letters.
In a single line, output the lexicographically smallest word.
Example
( points): k = 0, ~|s_1|=|s_2|=\dots=|s_n|;
( points): k = 0, ~|s_i|\le 10;
( points): k = 0;
( points): n \le 500, ~|s_i|\le 10;
( points): n \le 1000;
( points): |s_1|=|s_2|=\dots=|s_n|;
( points): s_i consists of letters and ;
( points): without additional restrictions.