你负责一场包含若干不同题目和总时间限制的程序设计竞赛。评委为每道题提供了阅读时间、编码时间和解题概率。

在比赛期间，参赛队伍可以查看排行榜，上面显示了每支队伍的通过提交情况。查看排行榜可能会影响队伍的策略！所有队伍在比赛中解决问题时都遵循以下策略：

1. 选择阅读一道题目。为了选择阅读哪道题，他们首先收集所有尚未阅读的题目（如果所有题目都已阅读，他们将在比赛剩余时间内什么都不做）。如果这些题目中没有任何题目有解，他们将随机均匀地选择一道题来阅读。否则，他们将根据每道题已有的解题数量进行加权随机选择。例如，如果有三道题 A、B、C，分别有 3、1 和 0 个解，他们选择阅读题目 A 的概率为 $\frac{3}{4}$，阅读题目 B 的概率为 $\frac{1}{4}$，阅读题目 C 的概率为 $\frac{0}{4}$。

2. 选择好题目后，他们首先阅读该题。这总是需要花费该题给定的阅读时间。阅读完题目后，他们会知道自己能否解决该题。队伍以给定的概率解决该问题（此过程不耗时）。如果他们无法解决该问题，队伍将回到第 1 步并选择另一道题来阅读。否则，他们将花费给定的时间来编写该题的代码（即使比赛剩余时间不足以完成），然后回到第 1 步选择另一道题来阅读。一旦队伍完成所选题目的编码，该题即被解决（接收判题结果不耗时）；每个题目的解都会影响排行榜，从而影响其他队伍尝试的题目。

在任何时刻，排行榜都会首先更新该时刻发生的所有解题情况，然后队伍会看到更新后的排行榜。

设 $f(m, i)$ 为当有 $m$ 支队伍参赛时，预计会有多少支队伍解决题目 $i$。设 $g(i) = \lim_{m \to \infty} [\frac{f(m, i)}{m}]$，这是当队伍数量足够多时，预计解决题目 $i$ 的队伍比例。请输出所有题目 $i$ 的 $g(i)$。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 17$) 和 $t$ ($1 \le t \le 100$)，其中 $n$ 是比赛中的题目数量，$t$ 是以分钟为单位的比赛时间限制。

接下来的 $n$ 行，每行包含两个整数 $r$ 和 $c$ ($1 \le r, c \le t$) 以及一个实数 $p$ ($0.0 \le p \le 1.0$)。每行描述一道题目，其中 $r$ 为阅读时间（分钟），$c$ 为编码时间（分钟），$p$ 为解决该题的概率。

输出格式

输出 $n$ 行。每行包含一个实数，表示在队伍数量足够多时，预计解决该特定题目的队伍比例。请按输入顺序输出这些比例。答案的绝对误差或相对误差不超过 $10^{-6}$。

样例

样例输入 1

4 42
10 10 0.75
10 10 0.75
10 12 1
10 12 1

样例输出 1

0.45625
0.45625
0.296875
0.296875

样例输入 2

4 42
10 12 0.75
10 12 0.75
10 10 1
10 10 1

样例输出 2

0.203125
0.203125
0.683238636363636
0.683238636363636

样例输入 3

5 100
40 60 0.6
40 61 1
10 40 0.3
10 40 0.4
10 40 0.5

样例输出 3

0.12
0
0.112628571428571
0.159739682539683
0.206444444444444