Longest Possible Wedding Email

Mike recently got married and, as we all know, his life has been filled with both happiness and some unexpected complications. In the past month he gained 70 pounds. Due to his fat fingers, when he types an email to his closest friend Slavik describing everything he ate during the day, sometimes he accidentally presses extra keys. However, Mike is careful: for every key he intends to press, the number of erroneous extra key presses (which may come before or after the intended key) is at most 3. Because Slavik repeatedly received emails that are difficult to read, he asked Mike to send the email three times so that it might be easier to decipher.

Your task is to help Slavik determine the longest possible original message that Mike might have written, given the three noisy emails he received.

How the emails are generated:

Each email is produced by a segmentation process. Assume that the intended message is a string T. When Mike types T, for every intended character, he types a block of 1 to 4 characters. In each block, the intended character appears at least once (possibly duplicated) and the extra characters (mistakes) in that block number at most 3. Moreover, the entire email is exactly the concatenation of these blocks; that is, if an email S has length n and T has length L, then the blocks have lengths l₁, l₂, …, l_L where each l_i satisfies 1 ≤ l_i ≤ 4 and the trailing unassigned characters (after the intended press) are also considered part of the same block (and their count is at most 3). In particular, if we mark the position (0-indexed) of the character chosen as the intended one in each block, and denote the previous block’s ending position as p (with p = -1 initially), then the chosen index i satisfies:

1 ≤ i - p ≤ 4

and after the last intended character at index i, the remaining characters (n - i - 1) must be at most 3.

Given three emails S₁, S₂, and S₃ (each produced with possibly different extra errors but according to the above rule) determine the longest string T such that for each email, there exists a valid segmentation whose intended letters form T.

The answer T is not necessarily unique; any longest string that can be obtained is acceptable.

Note: Any mathematical formulas must be written in LaTeX. For example, the constraint above can be written as:

$1 \le i - p \le 4$

inputFormat

The input consists of three lines. Each of the three lines contains a non‐empty string which represents one email. It is guaranteed that each email was generated by partitioning the email into blocks each of length between 1 and 4 as described.

You may assume that the lengths of the emails are such that a valid segmentation exists.

outputFormat

Output a single line containing the longest possible original message (string T) that is consistent with all three emails. If there are multiple answers, any one is acceptable. If no valid message exists, output an empty string.

sample

abc
abc
abc

abc