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 的鱼成为湖中最后一条鱼的概率。
示例
输入 #1
2 0 0.5 0.5 0
输出 #1
0.500000 0.500000
输入 #2
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
输出 #2
1.000000 0.000000 0.000000 0.000000 0.000000