Стародавні Рулони
Ви придбали 3 стародавні сувої у мага. Кожен сувій містить рядок однакової довжини. Маг пояснив, що ці сувої є копіями ключового рядка, необхідного для входу в підземелля з секретним скарбом. Однак, через численні ручні переписування, рядки можуть містити помилки, хоча їх довжина залишається правильною.
Ваше завдання — відновити оригінальний рядок з цих копій. Ви вирішили дотримуватися наступних припущень:
Кожен скопійований рядок може містити не більше d помилок. Це означає, що відстань Хеммінга між оригінальним рядком і будь-яким скопійованим рядком не перевищує d.
Якщо існує кілька можливих варіантів, оригінальним вважається лексикографічно найменший рядок.
Чи зможете ви відновити оригінальний рядок?
Вхідні дані
Вхід містить кілька наборів даних.
Кожен набір даних має такий формат:
l d
str_1
str_2
str_3
Перший рядок містить два цілі числа l (1 ≤ l ≤ 100000) та d (0 ≤ d ≤ 5000). l вказує на довжину кожного з 3 рядків, а d визначає максимальну допустиму відстань Хеммінга. Наступні 3 рядки містять самі рядки, кожен з яких має довжину l. Усі рядки складаються лише з малих та великих літер англійського алфавіту.
Вхід завершується рядком з двома нулями, який не потрібно обробляти.
Вихідні дані
Виведіть лексикографічно найменший рядок, що відповідає умовам. Якщо жоден рядок не задовольняє умови, виведіть "-1".