the-curse-of-district-b12

There exists a cursed city known as District B12. It consists of N people upon which an ancient curse prevails and due to which they have turned into monsters. When normal residents meet at day, they greet each other but brace yourself,  this city is not normal, it's cursed,  at night people turn into monsters and try to kill whoever they meet.

Whenever two monsters meet they fight until one of them dies.

Every night one pair of monsters meet, and the probability of each pair meeting is the same.

If two people with indexes i and j meet, the first will kill the second with the probability Pij, and the second will kill the first with the probability Pji = 1 - Pij.

The same process goes on until only one cursed monster is alive in the whole city.

For each monster, find out the probability that he/she will survive till the last.

Input Format
The first line contains N, the number of monsters at the beginning.
N lines follow, each contains N real numbers (the matrix Pij where the j^th number in the i^th line gives the probability that the i^th monster will kill the j^th monster when they meet).

All diagonal elements are guaranteed to be 0 and it is guaranteed that Pji = 1 - Pij.

None of the probabilities will have more than 5 digits after the decimal.

Output Format
Print N numbers where the i^th number represents the probability that the i^th monster will survive to be the last one standing. All values should be accurate to 5 digits after the decimal place.

Constraints
1 ≤ N ≤18

0 ≤ Pij ≤1

SAMPLE INPUT
5
0 0.5 0.5 0 0.5
0.5 0 0.5 0 0.5
0.5 0.5 0 0 0.5
1 1 1 0 1
0.5 0.5 0.5 0 0

SAMPLE OUTPUT
0.00000 0.00000 0.00000 1.00000 0.00000

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: