Krillin the Krill is a data-scientist working at Big Krill and wants to study the Krillboard Hot 100, which charts the popularity of ~m~ songs.

Instead of traditional rankings, the Krillboard measures popularity using a Krill Score.

In this system, a lower score is better (a score of 1 is vastly more popular than a score of 100). A song's Krill Score is completely independent of other songs, meaning one song's score changing does not force another song's score to change.

Through Krillin's deft ML skills, he has determined that each week, the ~i~'th song has:

• A probability of ~u_i~% to get more popular (its Krill Score decreases by 1).
• A probability of ~d_i~% to get less popular (its Krill Score increases by 1).
• Otherwise, its score does not change.

For each song, calculate its expected Krill Score after exactly ~n~ weeks. The predicted Krillboard chart is formed by sorting songs in increasing order of their expected score (best scores first).

If two songs have the exact same expected score, the song with the lexicographically smaller title comes first (e.g., "apple" beats "zebra").

Expected scores do not need to be whole numbers. They may be fractional or even negative.

Input

The first line begins with two integers ~m~ and ~n~ ~(1 \le m \le 10^5, 1 \le n \le 10^9)~, the number of songs and the number of weeks.

The next ~m~ lines each contain a string ~S_i~ and three integers ~c_i, u_i, d_i~:

• ~S_i~ is the title of the song. It consists only of lowercase English letters and has length from ~1~ to ~15~. It is guaranteed that all song titles are unique;
• ~c_i~ ~(1 \le c_i \le m)~ is the current Krill Score of the song;
• ~u_i~ ~(0 \le u_i \le 100)~ is the probability that the song gets more popular in one week;
• ~d_i~ ~(0 \le d_i \le 100)~ is the probability that the song gets less popular in one week.

It is guaranteed that ~u_i + d_i \le 100~. It is also guaranteed that the initial scores ~c_i~ happen to form a permutation of the integers from ~1~ to ~m~.

Output

Output ~m~ song titles separated by spaces on a single line in the order of the predicted Krillboard chart.

Example

Input 1

3 10
lovetakesmiles 1 10 50
taxes 2 80 0
cobra 3 20 20

Output 1

taxes cobra lovetakesmiles

• lovetakesmiles starts with a score of ~1~. In the first week, it has a ~10%~ chance to improve (score becomes ~0~), a ~50%~ chance to worsen (score becomes ~2~), and a ~40%~ chance to stay the same (score remains ~1~). Its expected score after ~1~ week is ~(0.10 \times 0) + (0.50 \times 2) + (0.40 \times 1) = 1.4~. Continuing this process, its expected score after ~10~ weeks evaluates to exactly ~5~.
• taxes starts with a score of ~2~. In the first week, it has an ~80%~ chance to improve (score becomes ~1~), a ~0%~ chance to worsen (score becomes ~3~), and a ~20%~ chance to stay the same (score remains ~2~). Its expected score after ~1~ week is ~(0.80 \times 1) + (0.00 \times 3) + (0.20 \times 2) = 1.2~. After ~10~ weeks, its expected score evaluates to ~-6~.
• cobra starts with a score of ~3~. Its probabilities of improving and worsening cancel each other out exactly, so its expected score after ~10~ weeks remains ~3~.

Sorting them by expected score in increasing order ~(-6, 3, 5)~ gives the final chart order: taxes, cobra, lovetakesmiles.

Input 2

5 1000
krillofyou 1 0 100
krillinglights 2 50 50
krillsummer 3 100 0
krillofafeather 4 30 20
krillineed 5 10 10

Output 2

krillsummer krillofafeather krillinglights krillineed krillofyou