Amazon Regex Generator

You are given uppercase strings x, y, z, each of length n. A regex is built from single uppercase letters or bracketed character classes, with no repeated letters inside a class, and the whole regex is concatenated position by position. Find the longest regex that matches both x and y but does not match z; if several answers have the same length, output the lexicographically smallest one; if none exists, output -1.

输入格式

The first line contains n (1≤n≤1000000); the next three lines are x, y, z in order, each containing exactly n uppercase English letters A-Z.

输出格式

Output the longest, lexicographically smallest regex that matches x/y but does not match z; if there is no solution, output -1.

样例 1

输入：

3
AAA
BBB
CCC

输出：

[ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABDEFGHIJKLMNOPQRSTUVWXYZ]

样例 2

输入：

4
ABCA
BCAB
CAAC

输出：

[ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABDEFGHIJKLMNOPQRSTUVWXYZ]

样例 3

输入：

3
AZA
ZAZ
AAA

输出：

-1