Sakurako and Old Dictionary

Sakurako is tidying the room. He has found a dictionary which contains $n$ 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: $\text{‘‘a’’, ‘‘b’’, ‘‘ab’’}$, the possible words are: $\text{‘‘abab’’, ‘‘aabb’’, ‘‘baab’’, ‘‘baba’’, ‘‘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 $k$ strings are reversed.

Help Sakurako find the lexicographically smallest possible word in modern life.

Input

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 $n$ 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.

Output

In a single line, output the lexicographically smallest word.

Examples

Scoring

1. ($28$ points): $k=0,|s_1|=|s_2|=\cdots =|s_n|$;

2. ($39$ points): $k=0,|s_i|\le 10$;

3. ($72$ points): $k=0$;

4. ($63$ points): $n\le 500,|s_i|\le 10$;

5. ($79$ points): $n\le 1000$;

6. ($54$ points): $|s_1|=|s_2|=\cdots =|s_n|$;

7. ($91$ points): $s_i$ consists of letters $\text{‘a’}$ and $\text{‘b’}$;

8. ($74$ points): without additional restrictions.