Regular Expressions
Time limit 	10 seconds
Memory limit 	256Mb
Input 	standard input or input.txt
Output 	standard output or output.txt

Pavel doesn’t have a college education. He’s a natural programmer. He loves brief, laconic bits of code more than anything else in the world. One-liners are his favorite! Striving for shorter code he often makes use of regular expressions. There is nothing more creative and enjoyable than working on yet another regular expression in the middle of the night.

But bummer. Pavel’s colleague, Simon, is often unhappy with Pavel’s code. Simon never uses regular expressions in his code. He’s just jealous! If he knew a thing about regular expressions, he wouldn’t complain.

Once Pavel was careless to remark that Simon is not creative enough to build complex regular expressions. Simon replied, quite sacrilegiously, that there was nothing creative about regular expressions. Their argument evolved into a competition: they decided to find out who would be the fastest to write a regular expression matching a defined set of strings. Simon wants to win by creating a program which would solve this problem automatically, thus proving the lack of creative component in the process. Their friend Peter, a bioinformatician, will be the judge.

Simon glanced at the syntaxis of Perl regular expressions and was horrified: is this what programmers have done to a simple and elegant concept? Simon graduated from the mathematics department of the university and has always thought that a regular expression is the following:

    0 (zero character) — a regular expression that matches no string.
    a, g, t, c (letter) — a regular expression matching precisely one string: a single-letter string with the same letter as that in the expression.
    If R and P are regular expressions, then (R|P) is also a regular expression. It matches all strings which match at least one of the expressions R and P.
    If R and P are regular expressions, then (RP) is also a regular expression. It matches all strings which can be split in two in such a way that the first part matches the expression R, and the second part matches the expression P.
    If R is a regular expression, then (R*) is also a regular expression. It matches all strings which can be split into k >= 0 parts so that each part matches the expression R.

For instance, the regular expression (a*) matches any string containing only letters a, including an empty string. The regular expression (0*) only matches an empty string (which can be split into zero parts matching the expression 0). The regular expression (a|(g(tc))) matches two strings: a and gtc. Note that it is forbidden to omit or add extra brackets to regular expressions: it must contain strictly those pairs of brackets which appear during its construction according to the rules described above.

Simon wants a flawless victory by building the shortest matching regular expression. Help Simon. Write a program which finds the shortest regular expression for a set of strings, such that all these strings match the expression.