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

Обмеження: 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.

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