Best Battery

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka were choosing a battery for a very long time, but they couldn’t settle on a single option. In total, the online battery store’s catalog contains \(n\) items. Since Zenyk and Marichka couldn’t choose the best battery based on other parameters, they decided to choose by name. Each battery in the catalog has its own unique name \(s_i\).

Marichka wants to add her favorite letter to each battery name. She wants to insert it at the beginning of the name, at its end, or anywhere in the middle. Zenyk wants the battery name (with the single letter added by Marichka) to be lexicographically the smallest among all possible ones (see the Notes section for the definition of lexicographical order).

Your task: tell what is the smallest string Marichka and Zenyk can obtain. That is, you need to state which lexicographically smallest string can be obtained by adding Marichka’s favorite letter to exactly one of the strings \(s_i\).

Input

The first line contains a single integer \(n\) — the number of different batteries.

The second line contains a single Latin alphabet letter \(c\) — Marichka’s favorite letter.

The next \(n\) lines contain one string each — the battery names \(s_i\).

Output

In a single line, output the string — the lexicographically smallest string that can be obtained by adding one letter \(c\) to one of the strings \(s_i\).

Constraints

\(1 \le n \le 10^5\),

the total length of all \(s_i\) does not exceed \(10^5\),

\(c\) as well as all characters of the strings \(s_i\) are lowercase Latin letters,

all \(s_i\) are distinct.

Problem scoring consists of the following subtasks:

• 1 point — the first example from the problem statement,

• 1 point — the second example from the problem statement,

• 18 points — a group of tests in which \(1 \le n, |s_i| \le 10\),

• 40 points — a group of tests in which \(1 \le n \le 500\), and the total length of the strings does not exceed 1000,

• 40 points — a group of tests in which \(1 \le n \le 10^5\), and the total length of the strings does not exceed \(10^5\).

You will receive points for a subtask only if you give the correct answer to all tests in the subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
1 d ace	acde

Input (stdin) сopy	Output (stdout) сopy
4 z abc defg aasdf abcd	aasdfz

Notes

A string \(s\) is lexicographically smaller than a string \(t\) if:

• string \(s\) is shorter than string \(t\), and also completely matches the prefix of string \(t\) of the same length as string \(s\);

• in string \(s\), the first character in which \(s\) and \(t\) differ comes earlier in the alphabet than the corresponding character in string \(t\).

For example: abc \(<\) abcdefg, bbacd \(<\) bbaxyz.

Lexicographical comparison is implemented by the < operator in most popular programming languages.