Стародавні Сувої#4300

Стародавні Сувої

20 секунд

256 мегабайтів

Складна

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

Ваше завдання — відновити оригінальний рядок з цих копій. Ви вирішили дотримуватися наступних припущень:

Кожен скопійований рядок може містити не більше $d$ помилок. Це означає, що відстань Хеммінга між оригінальним рядком і будь-яким скопійованим рядком не перевищує $d$ .
Якщо існує кілька можливих варіантів, оригінальним вважається лексикографічно найменший рядок.

Чи зможете ви відновити оригінальний рядок?

Вхідні дані

Вхід містить кілька наборів даних.

Кожен набір даних має такий формат:

$l$ $d$

$s t r_{1}$ str_1

$s t r_{2}$ str_2

$s t r_{3}$ str_3

Перший рядок містить два цілі числа $l$ ( $1 \leq l \leq 100000$ 1 \le l \le 100000) та $d$ ( $0 \leq d \leq 5000$ 0 \le d \le 5000). $l$ вказує на довжину кожного з $3$ рядків, а $d$ визначає максимальну допустиму відстань Хеммінга. Наступні $3$ рядки містять самі рядки, кожен з яких має довжину $l$ . Усі рядки складаються лише з малих та великих літер англійського алфавіту.

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

Вихідні дані

Виведіть лексикографічно найменший рядок, що відповідає умовам. Якщо жоден рядок не задовольняє умови, виведіть "-1".

Приклади

Приклад 1