On a number line there are n balls. At time moment 0 for each ball the following data is known: its coordinate x_i, speed v_i (possibly, negative) and weight m_i. The radius of the balls can be ignored.

The balls collide elastically, i.e. if two balls weighing m₁ and m₂ and with speeds v₁ and v₂ collide, their new speeds will be:

$\text{[math]}$ .

Your task is to find out, where each ball will be t seconds after.

Input

The first line contains two integers n and t (1 ≤ n ≤ 10, 0 ≤ t ≤ 100) — amount of balls and duration of the process. Then follow n lines, each containing three integers: x_i, v_i, m_i (1 ≤ |v_i|, m_i ≤ 100, |x_i| ≤ 100) — coordinate, speed and weight of the ball with index i at time moment 0.

It is guaranteed that no two balls have the same coordinate initially. Also each collision will be a collision of not more than two balls (that is, three or more balls never collide at the same point in all times from segment [0;t]).

Output

Output n numbers — coordinates of the balls t seconds after. Output the numbers accurate to at least 4 digits after the decimal point.

Collisions

Examples