Find Longest Regex

A regular expression consists of uppercase letters and bracketed character classes; letters within a class must not repeat, and one class matches one character. Given x, y and z of equal length, find the longest regular expression that matches x and y but not z; among equal lengths take the lexicographically smallest. If there is no solution, output −1.

输入格式

Three lines x, y and z, containing only uppercase English letters, each of length n (1..1000000). Lexicographic order follows ASCII character order.

输出格式

Output the regular expression string, or −1.

样例 1

输入：

AB
BD
CD

输出：

[ABDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ]

样例 2

输入：

A
B
A

输出：

-1

样例 3

输入：

AA
AA
BB

输出：

[ABCDEFGHIJKLMNOPQRSTUVWXYZ][ACDEFGHIJKLMNOPQRSTUVWXYZ]

样例说明

Example 1: at the second position z=D is also the character of y, so it cannot be removed; at the first position C is removed, and all other letters of both character classes are kept, so the expression still matches AB and BD but not CD. Example 2: z equals x, so any expression matching x also matches z; there is no solution. Example 3: B could be removed at any position; to make the result lexicographically smallest, remove B only in the rightmost character class.