Background

This problem is an ancient NOI original problem. It has not been proven whether there is a reliable correct solution that can pass.

In daily computer operations, it is often necessary to perform operations on some of the files in the current directory. For example, copying all text files in the current directory to another directory, deleting all files in the current directory whose names start with a, and so on.

Problem Description

Many operating systems use regular expressions to implement file matching. A simple regular expression consists of English letters (case-sensitive), digits, and the wildcards * and ?. ? represents any single character, while * can represent zero or any number of characters.

For example:

1. a*b can match acb (* represents c), aabb (* represents ab), asdsfdfdb (* represents sdsfdfd), and ab (* represents no character).
2. a*b cannot match ac (missing the rightmost letter b), bb (missing the leftmost letter a), or abbc (the rightmost letter is not b).
3. a?b can match acb (? represents c).
4. a?b cannot match ab (missing the middle character) or accb (? can only represent one character).

Now we want to operate on some files in a directory. Write a program to find a regular expression such that it matches as many files to be operated on as possible, but it must not match any file that should not be operated on. Note that the optimal regular expression you find should have the shortest length.

If there are multiple optimal regular expressions with the shortest length, any one of them is acceptable.

Input Format

The first line contains an integer $n$, indicating the number of strings.

The next $n$ lines each contain a string and a character (+ or -), indicating the file name (consisting of English letters and digits; English letters are case-sensitive) and whether to operate on it (+ means the file should be operated on, - means it should not be operated on).

Output Format

The first line contains an integer, indicating the number of files that can be matched by the optimal regular expression you found.

The second line contains a string, indicating the regular expression you found.

5
EXCHANGE +
EXT +
HARDWARE +
MOUSE -
NETWORK -

2
E*

5
EXCHANGE +
EXTRAS +
HARDWARE +
MOUSE -
NETWORK -

3
*A*

Hint

For $5\%$ of the testdata: $n=5$.
For $25\%$ of the testdata: $5\le n\le 23$.
For $55\%$ of the testdata: $5\le n\le 54$.
For $75\%$ of the testdata: $5\le n\le 160$.
For $100\%$ of the testdata: $5\le n\le 250,\ |S_i|\le8$.

To make it easier to debug and verify the correctness of the Special Judge, the wrong feedback messages and their meanings are provided:

1. The number of matching file name(s) is wrong! The number you output is not the maximum.
2. The expression is longer than jury's expression! The expression you output is not the shortest.
3. The expression matches an invalid file name! The expression you output matches a file that should not be operated on.
4. The answer is correct. The expression you output meets the requirements.
5. The expression is shorter than jury's expression ??? The expression you output meets the requirements and is shorter than the current optimal expression.
6. The expression is better than jury's expression ??? The expression you output meets the requirements and matches more files than the current optimal expression.
7. The number of matching file name(s) is false! The number of files matched by your expression is less than the number you output.

If you encounter evaluation errors of type 5 or 6, please contact the problem porter or an administrator, and we will fix the data.

Thanks for the Special Judge source: Sprague_Garundy.

Thanks for the hack testdata provider: oOoOoOOOooOO, placed in a separate Subtask and not scored.

Translated by ChatGPT 5