Найкращий акумулятор

Обмеження: 2 сек., 256 МіБ

Зеник та Марічка дуже довго вибирали акумулятор, проте так і не змогли зупинитися на єдиному варіанті. Загалом каталог інтернет-магазину акумуляторів містить $n$ позицій. Оскільки вибрати найкращий акумулятор по інших параметрах Зеник та Марічка не змогли, то вони вирішили вибирати по назві. Кожен акумулятор з каталогу має свою унікальну назву $s_i$.

Марічка хоче додати свою улюблену літеру до кожної назви акумулятора. Вона хоче вставити її на початок назви, в її кінець, або будь-куди в середину. Зеник хоче, щоб назва акумулятора (з однією доданою Марічкою літерою) була лексикографічно найменшою серед усіх можливих (дивіться розділ Примітки для визначення лексикографічного порядку).

Ваше завдання: сказати який найменший рядок Марічка та Зеник можуть дістати. Тобто, потрібно сказати, який лексикографічно найменший рядок можна дістати, якщо додати до одного із рядків $s_i$ рівно улюблену літеру Марічки.

Вхідні дані

Перший рядок містить одне ціле число $n$ — кількість різних акумуляторів.

Другий рядок містить одну літеру латинського алфавіту $c$ — улюблену літеру Марічки.

Наступні $n$ рядків містять по одному рядку кожен — назви акумуляторів $s_i$.

Вихідні дані

В єдиному рядку виведіть рядок — лексикографічно найменший рядок який можна отримати додаванням до одного з рядків $s_i$ однієї літери $c$.

Обмеження

$1 \le n \le 10^5$,

загальна довжина усіх $s_i$ не перевищує $10^5$,

$c$ а також усі символи рядків $s_i$ — маленькі літери латинського алфавіту,

усі $s_i$ різні.

Оцінювання задачі складається із наступних блоків:

• 1 бал — перший приклад з умови,

• 1 бал — другий приклад з умови,

• 18 балів — блок тестів у яких $1 \le n, |s_i| \le 10$,

• 40 балів — блок тестів у яких $1 \le n \le 500$, а також загальна довжина рядків не перевищує 1000,

• 40 балів — блок тестів у яких $1 \le n \le 10^5$, а також загальна довжина рядків не перевищує $10^5$.

Бали за блок ви отримаєте, лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 d ace	acde

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 z abc defg aasdf abcd	aasdfz

Примітки

Рядок $s$ є лексикографічно меншим за рядок $t$, якщо:

• рядок $s$ є коротшим за рядок $t$, а також повністю збігається з початком рядка $t$ такої ж довжини як рядок $s$;

• у рядку $s$ перший символ у якому $s$ та $t$ відрізняються йде раніше в алфавіті ніж відповідний символ у рядку $t$.

Наприклад: abc $<$ abcdefg, bbacd $<$ bbaxyz.

Лексикографічне порівняння реалізоване оператором < в більшості популярних мовах програмування.