|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|8 초 (추가 시간 없음)||256 MB||6||3||3||50.000%|
You bought 3 ancient scrolls from a magician. These scrolls have a long string, and the lengths of the strings are the same. He said that these scrolls are copies of the key string to enter a dungeon with a secret treasure. However, he also said, they were copied so many times by hand, so the string will contain some errors, though the length seems correct.
Your job is to recover the original string from these strings. When finding the original string, you decided to use the following assumption.
Can you find the orignal string?
The input contains a series of datasets.
Each dataset has the following format:
l d str1 str2 str3
The first line contains two integers \(l\) (\(1 \leq l \leq 100,000\)) and \(d\) (\(0 \leq d \leq 5,000\).) \(l\) describes the length of 3 given strings and \(d\) describes acceptable maximal Hamming distance. The following 3 lines have given strings, whose lengths are \(l\). These 3 strings consist of only lower and upper case alphabets.
The input ends with a line containing two zeros, which should not be processed.
Print the lexicographically minimum satisfying the condition in a line. If there do not exist such strings, print
3 1 ACM IBM ICM 5 2 iwzwz iziwi zwizi 1 0 A B C 10 5 jLRNlNyGWx yyLnlyyGDA yLRnvyyGDA 0 0
ICM iwiwi -1 AARAlNyGDA