Automatic Input Verifier#1919

Automatic Input Verifier

2 seconds

256 megabytes

Very hard

Tons and tons of programming contest problems use input where integers are separated by spaces and newlines. In many cases, the number of numbers in the file and on each particular line is determined by the numbers themselves.

More formally, we define an input description as a sequence of statements of the following types:

"The first/next line contains $number$ non-negative integer(s), $variable_{1}$ \textit{variable}_1, $variable_{2}$ \textit{variable}_2, ..., $variable_{number}$ \textit{variable}_\textit{number}." Here, $number$ is a positive integer between $1$ and $3$ , and $variable$ s are distinct variable names that have not appeared before in the input description. When $number = 1$ \textit{number}=1, "integer(s)" should be replaced by "integer", otherwise by "integers".
"The first/next line contains $variable$ integers." Here, $variable$ is a variable name that has appeared in this description before this statement.
"The first/next line contains a non-negative integer $variable$ , followed by $variable$ integers." Here, $variable$ is a variable name that has not appeared before this statement and will not appear after it in the input description. Note that the same variable name appears twice in this statement.
"The first/next line contains $number$ integer(s)." Here, $number$ is a positive integer. When $number = 1$ \textit{number}=1, "integer(s)" should be replaced by "integer", otherwise by "integers".
"The first/next $variable$ lines contain $number$ integer(s) each." Here, $variable$ is a variable name that has appeared in this description before this statement, and $number$ is a positive integer. When $number = 1$ \textit{number}=1, "integer(s)" should be replaced by "integer", otherwise by "integers".
"The first/next $variable_{1}$ \textit{variable}_1 lines contain $variable_{2}$ \textit{variable}_2 integers each." Here, $variable_{1}$ \textit{variable}_1 and $variable_{2}$ \textit{variable}_2 are (possibly the same) variable names that have appeared in this description before this statement.
"The first/next $variable_{1}$ \textit{variable}_1 lines contain a non-negative integer $variable_{2}$ \textit{variable}_2, followed by $variable_{2}$ \textit{variable}_2 integers each." Here, $variable_{1}$ \textit{variable}_1 is a variable name that has appeared in this description before this statement. $variable_{2}$ \textit{variable}_2 is a variable name that has not appeared before and will not appear after this statement in this description, and is different from $variable_{1}$ \textit{variable}_1. Note that, unlike all other variables, $variable_{2}$ \textit{variable}_2 may have different values for each line described by this statement. This is useful, for example, to list several heaps where each heap has different number of items.

Each occurrence of "first/next" in the statements above should be replaced by "first" in the first statement of the input description, and by "next" in all following statements.

Given several input files, you need to check whether there exists an input description consisting of at most $4$ statements that matches most of the given input files and highlight the input files that do not fit the description.

Input

The first line of the input file contains an integer $n$ $(1 \leq n \leq 10)$ (1 \le n \le 10), the number of input files given. Note that in the rest of this statement, the term "input file" means a different thing than in the previous sentence — it refers to the file's content, not to the physical file.

Each input file description starts with a line containing a dash ("-"). Then comes the actual input file, with an exclamation mark ("!") appended to the end of each line to ease handling of empty lines.

After removing the exclamation mark, each line of each input file will contain between $0$ and $1000$ integers, each between $- 1000$ and $1000$ , separated by single spaces. Each given input file will contain at most $10000$ lines and at most $100000$ integers.

Output

If there exists an input description with at most $4$ statements that describes all given input files, output All good! (without quotes) on the first line, followed by the input description, one statement per line. Use non-empty strings of at most 10 lowercase English letters as variable names. If there are several possible descriptions, output any.

If there exists an input description with at most $4$ statements that describes at least one given input file, find any such description that describes the largest number of files. Output Bad format: $n u mb er s$ . (without quotes) on the first line, where $n u mb er s$ is a single-space separated list of input file indices (from $1$ to $n$ ) that do not fit. Then output the description.

If no input description with at most $4$ statements matches any input file, output FAIL. in the only line.

Examples

Example 1