Background

Special for beginners, ^_^

Description

话说小明等几个同学进了大学不认真学习，整天旷课打游戏，期末考试挂了十多门，被学校开除了。为了不让父母知道，只得沦为职业代练，让爱好变成职业（详见《高考647分的高材生,蜗居网吧4年不回家,不洗澡不换衣服》）。本题就是请你计算下，预期收入最高的三个职业代练的编号和收入。

Format

Input

第一行给出一个t（不超过一万，表示可以代练的任务数量）和p（不超过100，表示职业代练的数量）。接下来t行，每行给出三个整数s、e（0 ≤ s < e ≤ 10000）和a（不超过100），分别表示代练任务的开始时间、结束时间以及如果完成这一任务能得到的收入。注意，代练也有职业道德，不允许一个人同时代练多个任务，也不允许提前结束一个任务，但是同时结束一项旧任务开始一项新任务是可以的。任务描述后面是每个代练完成每项任务的概率（如果没有完成任务，一分没有，徐老师说了，今天不好好学习，以后就得被社会毒打，没有苦劳一说的）。第一个t行是第一个代练的，以此类推，一共t*p行。题目保证所有输入都合法。

Output

按照预期收入降序输出预期收入最高的3个代练的编号和预期收入（保留到百分位）。

Samples

3 4 
0 3 50
3 6 50
0 6 75
0.2
0.3
0.6
0.6
0.6
0.5
0.6
0.5
0.4
0.9
0.9
0.9

4 90.00 
2 60.00
3 55.00

Limitation

1s, 1024KiB for each test case.