Description

In the human nervous system, each signal can be represented by $−1$ or $+1$. These signals combine to eventually form complex information such as joy, anger, sorrow, and happiness; sour, sweet, bitter, and spicy; red, yellow, green, and blue. Breakthroughs in nano-probing technology have enabled biologists to measure the complete logical function of specific regions of the brain. However, processing ultra-large data has always been a headache for Professor H.

Suppose a logical unit accepts $N$ signal inputs and produces a real value $r$ representing some meaning. Then there are $2^N$ possible cases in total. Through long-term cumulative measurements, Professor H can accurately obtain the mapping between input signals and $r$:

Further research has found that the neuron’s computation can be modeled as a well-known polynomial. Since the square of an input signal value is always $1$, we can uniquely represent any logic $f$ by a polynomial without powers consisting of $2^N$ terms.

For example x1=+1; x2=+1 -> 0

x1=+1; x2=-1 -> 1

x1=-1; x2=+1 -> 2

x1=-1; x2=-1 -> 3

can be written as

Studying the polynomial form of a logical unit is very meaningful for understanding how the brain works, so Xiao M decided to help Professor H convert all measured logic tables into polynomial form. Such a simple task should be no problem for the coding ace Xiao M, right?

Input Format

The first line is $N$ ($1\le N \le20$). Then there are $2^N$ lines. Each line contains one set of logical inputs and one corresponding value, representing the signs of $x_1...x_N$ and the corresponding $r$. See the sample. The testdata guarantees that the absolute value of every logical value does not exceed $100$, and it contains no more than $2$ decimal places. All logical input strings are guaranteed to be pairwise distinct.

Output Format

Up to $2^N$ lines, representing the coefficient of each term in the polynomial. If a coefficient is an integer, output it in integer form; otherwise, output it as an irreducible fraction. If a coefficient is exactly $0$, omit the entire line. Separate variables and the coefficient with a space; the constant term should not have a space.

Order by the polynomial’s lexicographic order:

1. The constant term comes first.

2. Among non-constant terms, the term with the smaller smallest $x$ index comes first.

3. If two terms share the same smallest index, remove that smallest-indexed $x$ and compare recursively using the same rule.

Example: $1$, $x1$, $x1x2$, $x1x2x3$, $x1x3$, $x2$, $x2x3$, $x3$. See the sample.

2 
++ 0 
+- 1 
-+ 2 
-- 3 
 

3/2 
-1 x1 
-1/2 x2 

3 
--- -1.0
-++ -1.0
+-+ -1.0
++- -1.0
--+ 1.0
-+- 1.0
+-- 1.0
+++ 1.0

1 x1x2x3

Hint

This problem has $10$ testdata.

For the $1$st testdata, $N\le3$; for the $2$nd testdata, $N\le8$; for the $3$rd and $4$th testdata, $N\le11$; for the $5$th and $6$th testdata, the answer polynomial has only one nonzero term, as in Sample #2; for the $7$th and $8$th testdata, the answer polynomial has at most $5$ nonzero terms.

For $100\%$ of the testdata, $1 \le N \le 20, |r| \le 100, 100r\in \mathbb{Z}$.

Friendly reminder

Please pay attention to input and output efficiency.

Translated by ChatGPT 5