Word Snake: Longest Overlap Chain

In the word snake game, you are given a list of words and a starting letter. Your goal is to form the longest possible chain ("snake") by connecting words according to the following rules:

• You may use each word at most twice.
• When joining two words, choose a positive integer k such that:
• 1 ≤ k < length(word1) and 1 ≤ k < length(word2).
• The last k letters of the first word are exactly equal to the first k letters of the second word (i.e. the overlapping segment).
• The overlapping segment must be a proper part of both words (i.e. it cannot be equal to the entire word). For example, the words at and atide cannot be connected because using the only possible overlap (at) makes the first word completely overlapped.
• When two words are joined, the overlapping segment is merged into one. For example, joining beast and astonish via k = 3 (since beast ends with ast and astonish starts with ast) produces beastonish.

Your task is to output the longest possible resulting string (snake) which starts with the given starting letter. If there are several chains with the same maximum length, output any one of them.

Note on Overlaps: The overlap length k must be chosen so that it is strictly less than the length of each word involved, ensuring that the overlapped segment does not equal an entire word.

inputFormat

The input is given in the following format:

N
c
word1
word2
... 
wordN

Where:

• N is a positive integer representing the number of words.
• c is a lowercase English letter representing the required starting letter of the snake (i.e. the first letter of the first word in the chain).
• Each of the next N lines contains a word comprised of lowercase English letters.

outputFormat

Output a single string — the longest concatenated word chain obtainable by connecting the words following the above rules.

sample

3
a
ab
bc
ca

abca