Problem A
Fair Bandwidth Sharing

Orange tabby cat.

Dreaming of revolutionizing the tech industry and making the world a better place, Ging has recently moved to Silicon Valley to found his own startup, Katbook.

Katbook allows users to download cat pictures. Katbook is capable of transferring $t$ bits per second.

There are $n$ species of cats, numbered from $1$ to $n$. There is a demand ratio $d_i$ for the pictures of the $i$-th species. This means, if there is no further restrictions, the $i$-th cat species should have a ‘fair share’ of $\frac{d_i}{\sum _{j=1}^n{d}_j}$ fraction of the total bandwidth $t$.

However, because of infrastructure limitations, the bandwidth for the $i$-th species must be between $a_i$ and $b_i$.

You are newly hired by Ging as a network engineer at Katbook. Your first task is to find the most ‘fair’ bandwidth allocation satisfying the above constraints. More formally, let $x_i$ be the bandwidth allocated for downloading pictures of the $i$-th species. You must find $x_i$ such that:

• $a_i\le x_i\le b_i$,

• $\sum _{i=1}^n{x}_i=t$,

• Let $y_i=t\cdot \frac{d_i}{\sum _{j=1}^n{d}_j}$ ($y_i$ is the ‘fair share’ bandwidth, if there was no constraints regarding $a_i$ and $b_i$), the value $\sum _{i=1}^n\frac{(x_i-y_i{)}^2}{y_i}$ should be as small as possible.

Input

The first line of input contains $2$ integers $n$ and $t$ $(1\le n\le {10}^5,1\le t\le {10}^6)$.

In the next $n$ lines, the $i$-th line contains $3$ integers $a_i$, $b_i$ and $d_i$ $(0\le a_i\le b_i\le {10}^6,0<b_i,1\le d_i\le {10}^6)$.

It is guaranteed that there exists at least one valid solution.

It can be shown that under these constraints, the solution is unique.

Output

Output $n$ lines, each line contains the allocation for downloading pictures of the $i$-th species. The answer will be accepted if and only if its relative or absolute error to the optimal solution is at most ${10}^{-6}$.

Formally, for each line, let your answer be $a$, and the jury’s answer be $b$. Your answer is accepted if and only if $\frac{|a-b|}{max(1,|b|)}\le {10}^{-6}$.

Explanation of Sample input

In the first sample, each cat species has its ‘fair share’ of $\frac{1}{3}$ of the whole bandwidth.

In the second sample, note that the cat species $1$ has much more demand and could get almost all of the available bandwidth if not for its maximum to be capped at $1$. The rest is divided with ratio $2:1$, hence the cat species $2$ gets $6$ bits per second and the cat species $3$ gets $3$ bits per second.

3 10
0 10 1
0 10 1
0 10 1

3.33333333
3.33333333
3.33333333

3 10
0 1 1000
2 8 2
2 8 1

1.00000000
6.00000000
3.00000000