Minimal Boolean Expression

In this problem, you are given the truth table of an n-variable Boolean function A. The function A maps each combination of truth values for n propositions (each denoted by a lowercase letter) to a truth value, either true (T) or false (F). You are to output a canonical form (also known as a "normal form") for A using only the three fundamental logical operators: negation (!), conjunction (&) and disjunction (|). All operators and operands should be represented in a single expression with the following grammar:

1. ::= | | | () |
2. ::= &
3. ::= |
4. ::= !
5. is any lowercase letter from a to z.

The precedence of the operators is defined as follows (from highest to lowest):

1. Parentheses: ( )
2. Negation: !
3. Conjunction: &
4. Disjunction: |

Thus, for example, the expression

a&b|a&c|b&c

is interpreted as

(a&b) | (a&c) | (b&c)

which is a possible canonical form for a three-variable Boolean function that is true whenever at least two of a, b, c are true.

A standard method to represent Boolean functions is to use the sum-of-products form. For each combination (minterm) for which A is true, you can form a product (AND) of literals (each variable or its negation). Then, a disjunction (OR) of these products yields an expression equivalent to A. However, note that there can be multiple correct canonical forms. Your task is to output one that is as short as possible (i.e. minimal in total character length).

Note on constants: If the function is identically true or false, output the constant T or F respectively.

All literal negations must be denoted by a leading exclamation mark (!) (e.g. !a) and the operators & and | must be used for conjunction and disjunction respectively. All formulas that include more than one product term do not need extra parentheses thanks to the provided operator precedence.

It is guaranteed that n is small enough to allow a brute-force minimization algorithm (e.g., using the Quine–McCluskey algorithm).

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10), the number of variables. The variables are assumed to be the first n lowercase letters starting from a. The next 2^n lines each contain n+1 tokens separated by spaces. The first n tokens represent the truth values (T or F) assigned to the variables a, b, c, ... in order, and the last token is the resulting function value (T or F) for that assignment.

outputFormat

Output a single line containing the minimal canonical Boolean expression representing the given function. Use only the operators !, &, and | with no extra spaces. If the function is identically true, output T; if it is identically false, output F.

sample

2
T T T
T F F
F T F
F F F

a&b