E. Рыбы
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
128 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В озере живет n рыб, пронумерованных от 1 до n. Каждый день ровно одна пара рыб встречается друг с другом, причем вероятности встречи каждой пары равны между собой. Если две рыбы с номерами i и j встретились, то первая съест вторую с вероятностью aij, а вторая первую –– с вероятностью aji = 1 - aij. Этот процесс продолжается, пока в озере остается хотя бы две рыбы. Для каждой рыбы посчитайте вероятность того, что она останется последней в озере.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 18) — число рыб в озере. Далее следует n строк по n вещественных чисел — матрица a. aij (0 ≤ aij ≤ 1) — вероятность того, что рыба с номером i съест рыбу с номером j. Гарантируется, что на главной диагонали матрицы стоят нули, а для всех остальных элементов выполняется: aij = 1 - aji. Все вещественные числа даны не более чем с 6 знаками после десятичной точки.

Выходные данные

Выведите n вещественных чисел, разделенных пробелами, с точностью не менее 6 знаков после точки. Число с номером i должно быть равно вероятности того, что рыба с номером i останется последней в озере.

Примеры
Входные данные
2
0 0.5
0.5 0
Выходные данные
0.500000 0.500000
Входные данные
5
0 1 1 1 1
0 0 0.5 0.5 0.5
0 0.5 0 0.5 0.5
0 0.5 0.5 0 0.5
0 0.5 0.5 0.5 0
Выходные данные
1.000000 0.000000 0.000000 0.000000 0.000000