Neural Polynomial Transformation

In the human nervous system, each signal is represented by either -1 or +1. These signals combine to form complex information such as emotions or sensory perceptions. With breakthroughs in nano-detection technology, biologists are now able to measure the complete logical function of specific areas of the brain. However, professor H has long been troubled by the challenge of processing the huge datasets obtained from these measurements.

Assume that a logic unit accepts N input signals and produces a real number r which represents some meaning. In total there are \(2^N\) cases. After long-term measurement, professor H accurately obtains the lookup table of the relationship between the input signals and r, i.e. a function

[ f : {-1,1}^N \to \mathbb{R} ]

Further research shows that the computation of a neuron can be modeled as a polynomial. Since the square of each input signal is always 1, any logic function \(f\) can be uniquely represented by a polynomial with \(2^N\) terms without exponents:

[ f(x_1,x_2,\dots,x_N)=\sum_{S\subseteq{1,2,\dots,N}}a_S\prod_{i\in S}x_i]

where the coefficients are computed by the inverse Walsh-Hadamard transform:

[ a_S=\frac{1}{2^N}\sum_{x\in{-1,1}^N}f(x)\prod_{i\in S}x_i. ]

For example, for \(N=2\), suppose the measurements are as follows:

• \(x_1=+1,\; x_2=+1 \to f=0\)
• \(x_1=+1,\; x_2=-1 \to f=1\)
• \(x_1=-1,\; x_2=+1 \to f=2\)
• \(x_1=-1,\; x_2=-1 \to f=3\)

The unique polynomial representation turns out to be:

[ f(x_1,x_2)=1.5-0.5x_2-x_1. ]

Your task is to convert the provided lookup table into its unique polynomial form. When printing the polynomial:

• The output must start with f(x_1,x_2,...,x_N)= immediately followed (without spaces) by the polynomial expression.
• Terms with a zero coefficient should be omitted.
• For non-constant terms, if the absolute value of the coefficient is 1, the coefficient is omitted (only the sign is retained).
• The terms should be concatenated together with a preceding '+' or '-' sign (except possibly the first term if it is positive).
• For the purpose of this problem, when listing the terms, use the following convention for ordering: the constant term (corresponding to the empty set) is printed first, and then for each subset, consider its bitmask representation where bit 0 corresponds to \(x_N\), bit 1 to \(x_{N-1}\), and so on. This ensures that for \(N=2\) the polynomial is printed as 1.5-0.5x_2-x_1.

inputFormat

The input begins with an integer \(N\) (\(1 \le N \le 10\)), representing the number of input signals. This is followed by \(2^N\) real numbers, each on a separate line, corresponding to the measured output \(f(x)\) for each combination of signals.

The order of the \(2^N\) inputs is defined as follows: the first combination corresponds to all signals being +1; subsequent combinations are determined by the binary representation of the index (with 0 signifying +1 and 1 signifying -1), where the most significant bit corresponds to \(x_1\). For example, when \(N=2\), the order is:

• Row 0: \(x_1=+1,\; x_2=+1\)
• Row 1: \(x_1=+1,\; x_2=-1\)
• Row 2: \(x_1=-1,\; x_2=+1\)
• Row 3: \(x_1=-1,\; x_2=-1\)

outputFormat

Output the polynomial representation of the function in a single line. The format should be:

f(x_1,x_2,...,x_N)=[polynomial expression]

The polynomial must be printed without any spaces. For example, if \(N=2\) and the polynomial is 1.5-0.5x_2-x_1, then that is the expected output.

sample

1
2
0

f(x_1)=1+x_1