Древние свитки
Вы приобрели 3 древних свитка у мага. Каждый из них содержит строку одинаковой длины. Маг утверждает, что эти свитки — копии ключевой строки, необходимой для входа в подземелье с секретным сокровищем. Однако, поскольку копии делались вручную многократно, в строках могут быть ошибки, хотя их длина остаётся правильной.
Ваша задача — восстановить оригинальную строку из этих копий. Для этого вы решили использовать следующее предположение:
В каждой копии может быть не более d ошибок. Иными словами, расстояние Хэмминга между оригинальной строкой и любой из копий не превышает d.
Если существует несколько возможных кандидатов, выберите лексикографически минимальную строку в качестве оригинальной.
Сможете ли вы определить оригинальную строку?
Входные данные
Входные данные содержат несколько наборов.
Каждый набор данных представлен в следующем формате:
l d
str_1
str_2
str_3
Первая строка содержит два целых числа l (1 ≤ l ≤ 100000) и d (0 ≤ d ≤ 5000). Здесь l — это длина каждой из 3 строк, а d — максимально допустимое расстояние Хэмминга. Следующие 3 строки содержат сами строки, каждая длиной l. Все строки состоят только из строчных и заглавных букв английского алфавита.
Ввод завершается строкой "0 0", которую не нужно обрабатывать.
Выходные данные
Выведите лексикографически минимальную строку, соответствующую условиям, в одной строке. Если такой строки не существует, выведите "-1".