在雇佣杀手的残酷世界里，竞争是无情的，每个人都在为生存而战。为了消除竞争，许多杀手甚至会去暗杀其他杀手。问题在于：在几名杀手试图互相残杀的情况下，谁能活下来，谁又会丧命？

杀手在执行任务前通常会制定周密的计划，包括针对同一个目标制定多次尝试，第二次尝试作为第一次失败后的备份，第三次尝试作为二次备份，以此类推。利用他们卓越的“歼灭分析”能力，杀手们可以非常准确地确定任何给定暗杀尝试成功的概率。

给定一组杀手的暗杀计划列表，求出在所有这些尝试结束后，每名杀手存活的概率。执行暗杀尝试的前提是该杀手仍然存活，因此如果杀手因为已经被暗杀而无法行动，则该尝试会被取消。

图片由 Cristian V. 提供，来自 flickr，采用 cc by-nd 协议

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，其中 $n$ ($1 \le n \le 15$) 是杀手的数量，$m$ ($0 \le m \le 1000$) 是计划的暗杀尝试次数。杀手的编号为 $1$ 到 $n$。

接下来 $m$ 行，每行包含两个整数 $i, j$ 和一个实数 $p$，表示杀手 $i$ 计划尝试暗杀杀手 $j$ ($1 \le i, j \le n, j \neq i$)，且该尝试成功的概率为 $p$ ($0 \le p \le 1$，小数点后最多 6 位)。计划的尝试按时间顺序从先到后列出，且没有两次尝试是同时发生的。

输出格式

输出 $n$ 行，第 $i$ 行包含杀手 $i$ 在所有 $m$ 次暗杀尝试结束后存活的概率。你可以假设这 $n$ 名杀手不会死于除这 $m$ 次尝试中被暗杀以外的任何其他原因。概率的绝对误差应不超过 $10^{-6}$。

样例

输入 1

4 3
1 2 0.25
1 4 0.42
2 3 1.0

输出 1

1
0.75
0.25
0.58

输入 2

2 3
1 2 0.23
2 1 0.99
1 2 0.99

输出 2

0.2377000000
0.7623770000