Optimal Regular Expression Selection

This problem involves generating a simple regular expression. The allowed characters are case‐sensitive English letters, digits, and two wildcards: * and ?. Here, ? represents exactly one arbitrary character, while * represents zero or more arbitrary characters.

You are given two groups of file names. The first group consists of files that need to be operated on (the target files). The second group consists of files that must not be operated on (the non-target files).

Your task is to find a regular expression such that:

• It matches as many target files as possible.
• It does not match any non-target file.
• Among all such regular expressions, its length is the shortest possible. (If there are several with minimum length, any one will be accepted.)

The matching follows standard wildcard rules. For example:

• a*b can match acb (with * representing c), aabb (with * representing ab), ab (with * representing an empty string), etc. However, it would not match ac (since the last character b is missing) nor abbc (if the final character is not b).
• a?b matches acb (with ? representing c), but does not match ab (missing the middle character) or accb (because ? represents exactly one character).

inputFormat

The input begins with an integer n on a single line, representing the number of target files. The following n lines each contain a non-empty string which is a file name (consisting of letters and digits, up to 100 characters).

The next line contains an integer m representing the number of non-target files, followed by m lines each containing a file name.

outputFormat

Output a single line containing the optimal regular expression that:

• Matches as many target files as possible, and
• Matches none of the non-target files.

If multiple regular expressions achieve the maximum number of matches, the one with the shortest length should be output. If there are several of minimum length, any one of them is acceptable.

sample

2
abc
abcd
1
ab

abc*