Minimal Well-Formed Formula

We are given a boolean function defined on ( n ) propositional variables ( P_0, P_1, \dots, P_{n-1} ). The function is provided by its truth table. A well–formed formula (WFF) is defined recursively as follows:

1. Every propositional variable ( P_i ) is a WFF whose truth table simply returns the ( i\text{-th} ) input value.
2. If ( A_1, A_2, \dots, A_k ) (( k \ge 1 )) are WFFs then ( (A_1 \land A_2 \land \cdots \land A_k) ) is a WFF whose truth value on any input ( I ) is ( \min{A_1(I), A_2(I), \dots, A_k(I)} ).
3. If ( A_1, A_2, \dots, A_k ) (( k \ge 1 )) are WFFs then ( (A_1 \lor A_2 \lor \cdots \lor A_k) ) is a WFF whose truth value on any input ( I ) is ( \max{A_1(I), A_2(I), \dots, A_k(I)} ).
4. If ( A ) is a WFF then ( \lnot A ) is a WFF whose truth value on input ( I ) is ( 1-A(I) ).

The size of a formula is defined as the number of occurrences of the operators (\land) and (\lor) (note that the negation (\lnot) does not count towards the size).

Given the truth table of a boolean function (i.e. a mapping from ({0,1}^n) to ({0,1})), your task is to output a well–formed formula whose truth table matches the given function and whose size is as small as possible.

Note: In the output formula, you should use the operators ∧ for (\land), ∨ for (\lor) and ¬ for (\lnot). Digits and variable names should be as shown (e.g. P0, P1, …).

inputFormat

The first line contains an integer ( n ) ((1 \le n \le 4)) representing the number of variables. The second line contains (2^n) space–separated integers (each either 0 or 1) representing the truth table of the function. The ( j\text{-th} ) number corresponds to the output on the ( j\text{-th} ) assignment (where the ( i\text{-th} ) input to the formula is the ( i\text{-th} ) bit of the binary representation of ( j ), with (0 \le j < 2^n)).

outputFormat

Output a single line containing the minimal well–formed formula (WFF) whose truth table is identical to the given boolean function. The formula must be constructed using only the allowed operations: ∧, ∨, and ¬. Parentheses must be used as shown in the grammar.

sample

1
0 1

P0