Ancient Scrolls

You bought three ancient scrolls from a magician. Each scroll carries one long string, and the three strings have the same length. The magician said the strings are copies of the key string that opens a dungeon holding a hidden treasure. People copied them by hand many times, so the strings contain errors and only the length is right.

Recover the original string from the three copies. Use these two assumptions.

• One copy contains at most $d$ errors. That is, the Hamming distance between the original string and each copy is at most $d$.
• If several strings satisfy the condition, the original string is the lexicographically smallest one among them.

The Hamming distance between two strings of the same length is the number of positions where the characters differ. The original string also consists of upper and lower case English letters, and strings compare by ASCII order, so every upper case letter comes before every lower case letter.

The input holds several datasets. Each dataset has this format:

l d
str1
str2
str3

The first line holds two integers $l$ ($1 \le l \le 100000$) and $d$ ($0 \le d \le 5000$). $l$ is the length of the three strings and $d$ is the largest acceptable Hamming distance. The next three lines hold the three strings, each of length $l$. The strings consist of upper and lower case English letters only.

The input ends with a line holding two zeros. Do not process that line.

For each dataset, print the lexicographically smallest string that satisfies the condition on its own line. If no such string exists, print -1.