리더보드 효과

여러분은 서로 다른 여러 문제와 전체 시간 제한이 있는 프로그래밍 대회를 운영한다. 심사위원은 각 문제의 읽기 시간, 코딩 시간, 해결 확률을 제공한다.

대회 중 팀은 각 팀의 정답 판정을 받은 제출을 보여 주는 리더보드를 볼 수 있다. 리더보드를 보는 것은 팀의 전략에 영향을 줄 수 있다. 모든 팀은 대회에서 문제를 풀 때 다음 전략을 따른다.

1. 읽을 문제를 고른다. 먼저 아직 읽지 않은 모든 문제를 모은다. 모든 문제를 읽었다면 남은 대회 시간 동안 아무것도 하지 않는다. 이 문제들 중 어떤 문제도 해결된 적이 없다면 그중 하나를 균등한 확률로 골라 읽는다. 그렇지 않다면 각 문제의 해결 수에 비례하는 확률로 읽을 문제를 고른다. 예를 들어 문제 A, B, C의 해결 수가 각각 $3$, $1$, $0$이면 문제 A를 $\frac{3}{4}$의 확률로, 문제 B를 $\frac{1}{4}$의 확률로, 문제 C를 $\frac{0}{4}$의 확률로 고른다.
2. 문제를 고른 뒤 먼저 그 문제를 읽는다. 읽는 데는 항상 그 문제의 읽기 시간이 걸린다. 문제를 다 읽으면 해결할 수 있는지 알게 된다. 팀은 주어진 확률로 그 문제를 해결할 수 있으며, 해결할 수 있는지 판단하는 데는 시간이 걸리지 않는다. 해결할 수 없다면 1단계로 돌아가 다른 문제를 골라 읽는다. 해결할 수 있다면 대회에 남은 시간이 그 문제를 끝내기에 부족하더라도 주어진 코딩 시간을 들인 뒤 1단계로 돌아가 다른 문제를 골라 읽는다. 팀이 고른 문제의 코딩을 마치면 그 문제는 해결된 것이며, 채점에 걸리는 시간은 없다. 각 문제의 해결은 리더보드에 영향을 주고, 따라서 다른 팀이 시도할 문제에도 영향을 준다.

어느 시점에서든 리더보드는 그 시점에 일어난 모든 해결로 먼저 갱신되고, 그다음에 팀이 갱신된 리더보드를 본다.

대회에 참가하는 팀이 $m$개일 때 문제 $i$를 해결하게 될 팀 수의 기댓값을 $f(m,i)$라고 하자. $g(i) = \lim_{m \rightarrow \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}$ 이하이면 정답으로 인정된다.