Description

MCPlayer542 has recently been studying "Quantum Computation and Quantum Information". He is very interested in the representation of quantum states.

Unlike classical bits, a qubit can not only be in the state $|0\rangle$ or the state $|1\rangle$, but can also be in a superposition state between $|0\rangle$ and $|1\rangle$.

The state of a quantum system composed of $n$ qubits is usually represented by a $2^n$-dimensional complex vector $|\psi\rangle$, where the product of the $i$-th complex number and its conjugate represents the probability of the state of these $n$ quantum bits being equal to the binary representation of $i$, after a quantum measurement on the computational basis.

For example, when you perform a quantum measurement on a two-qubit system represented by $|\phi\rangle=[\frac12,\frac12-\frac{\bf{i}}2,0,\frac{\bf{i}}2]^T$, it will be in the state $|00\rangle$ with a probability of $\frac12 \times \frac12 = \frac14$, in the state $|01\rangle$ with a probability of $(\frac12-\frac{\bf{i}}2) \times (\frac12+\frac{\bf{i}}2) = \frac14+\frac14 = \frac12$, in the state $|10\rangle$ with a probability of $0 \times 0 = 0$, and in the state $|11\rangle$ with a probability of $\frac{\bf{i}}1 \times (-\frac{\bf{i}}1) = \frac14$.

Now he has a quantum state $|\psi\rangle$ with $n$ quantum bits. Please help him calculate the probabilities of each qubit being in the states $|0\rangle$ and $|1\rangle$ after a measurement on the computational basis, respectively.

Input Format

The first line contains a positive integer $n$ ($1 \le n \le 8$), representing the number of quantum bits in the system.

The next $2^n$ lines contain the $i$-th line with two real numbers $a_i$ and $b_i$, separated by a space, representing the real part and the imaginary part of the $i$-th component of the quantum system vector, respectively.

The data guarantees that the sum of the probabilities of the quantum system being in all states does not exceed an absolute or relative error of $10^{-6}$ from $1$.

Output Format

Output $n$ lines, each containing two real numbers $p_0$ and $p_1$, separated by a space, representing the probabilities of each quantum bit being in the state $|0\rangle$ and the state $|1\rangle$ after the measurement, respectively.

Your output will be considered correct if and only if the absolute or relative error from the correct answer does not exceed $10^{-6}$.

2
0.5 0
0.5 -0.5
0 0
0 0.5

0.250000000 0.750000000
0.750000000 0.250000000