Leaderboard Effect

You are in charge of a programming contest with several distinct problems and an overall time limit. The judges provide a reading time, a coding time, and a solution probability for each problem.

During the contest, teams can view a leaderboard that shows the accepted submissions of each team. Seeing the leaderboard can affect teams' strategies. All teams follow this strategy when solving problems in the contest:

1. Choose a problem to read. First, they gather all problems they have not yet read. If they have read all problems, they spend the rest of the contest doing nothing. If none of these problems has any solutions, they choose one uniformly at random. Otherwise, they choose a problem to read with probability proportional to its number of solutions. For example, if problems A, B, and C have $3$, $1$, and $0$ solutions, respectively, they choose A with probability $\frac{3}{4}$, B with probability $\frac{1}{4}$, and C with probability $\frac{0}{4}$.
2. After choosing a problem, they first read it. This always takes that problem's reading time. After they finish reading, they know whether they can solve it. They can solve it with the given probability, and deciding whether they can takes no time. If they cannot solve it, they go back to step 1 and choose another problem to read. If they can solve it, they spend that problem's coding time, even if not enough contest time remains to finish, and then go back to step 1 to choose another problem to read. Once a team finishes coding the chosen problem, the problem is solved, and judging takes no time. Each solution affects the leaderboard, so it also affects the problems other teams attempt.

At every moment, the leaderboard first updates with all solutions that occurred at that moment, and then teams see the updated leaderboard.

Let $f(m,i)$ be the expected number of teams that solve problem $i$ if $m$ teams participate in the contest. Let $g(i) = \lim_{m \rightarrow \infty} \frac{f(m,i)}{m}$, the expected proportion of teams that solve problem $i$ when the number of teams is large enough. Output $g(i)$ for every problem $i$ in the set.

The first line contains two integers $n$ ($1 \le n \le 17$) and $t$ ($1 \le t \le 100$), where $n$ is the number of problems in the contest and $t$ is the time limit in minutes.

Each of the next $n$ lines contains two integers $r$ and $c$ ($1 \le r,c \le t$) and one real number $p$ ($0.0 \le p \le 1.0$). Each line describes one problem: $r$ is the reading time in minutes, $c$ is the coding time in minutes, and $p$ is the probability of solving the problem.

Output $n$ lines. Each line contains one real number: the expected proportion of teams that solve that problem when the number of teams is sufficiently large. Output the proportions for the problems in the same order as the input. Answers are accepted if their absolute or relative error is at most $10^{-6}$.