题目描述

湖中生活着 $n$ 条鱼，编号从 $1$ 到 $n$。

每天，恰好有一对鱼相遇，每一对鱼相遇的概率相同。如果编号为 $i$ 和 $j$ 的两条鱼相遇，编号为 $i$ 的鱼以概率 $a_{i,j}$ 吃掉编号为 $j$ 的鱼，编号为 $j$ 的鱼以概率 $a_{j,i}=1-a_{i,j}$ 吃掉编号为 $i$ 的鱼。

上述过程会一直持续，直到湖中只剩下一条鱼。请计算每条鱼成为湖中最后一条鱼的概率。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 18$），表示湖中的鱼的数量。

接下来有 $n$ 行，每行包含 $n$ 个实数，构成矩阵 $a$。$a_{i,j}$（$0 \leq a_{i,j} \leq 1$）表示编号为 $i$ 的鱼吃掉编号为 $j$ 的鱼的概率。

保证主对角线上的元素全为 $0$，且对于其他元素有 $a_{i,j} = 1 - a_{j,i}$。所有实数均保留不超过 $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