Description

Xiao Bo is a diligent college student who is very concerned about his academic performance. In each semester, he earns credits and corresponding grade points for several courses. Grade points are a way to measure course performance, while the average grade point (GPA) is an important indicator of a student's overall academic level. Xiao Bo hopes to achieve the highest possible GPA.

The school offers a special policy: each semester, students can choose to convert the grade of at most one course to a "Pass/No Pass" (PNP) mode (of course, they can also choose not to convert any course to PNP mode in certain semesters). In PNP mode, the grade points of this course will not be included in the GPA calculation.

Xiao Bo knows that he has taken a total of $n$ courses over $m$ semesters. He is aware of the credits, grade points, and semester for each course on his transcript, denoted as $s_i, g_i, t_i$. It is guaranteed that the first $2m$ courses on the transcript satisfy: the semester for the $i$-th course is $\lfloor \frac{i+1}{2} \rfloor$ (this ensures that at least two courses are taken each semester), while the semester for the remaining courses is not guaranteed. Xiao Bo hopes to make reasonable decisions each semester to maximize his final GPA.

However, Xiao Bo thinks that this is a bit too easy and wants to know: for any $k$ satisfying $2m \le k \le n$, if he only takes the courses from the $1$-st to the $k$-th on his transcript, considering the PNP decisions for each semester, what is the maximum GPA he can achieve?

The GPA calculation formula is as follows: assuming there are currently $n$ courses that have not chosen PNP mode, with the $i$-th course having credits and grade points of $s_i, g_i$, respectively, then

$$\text{GPA} = \frac{\sum_{i=1}^n s_i \cdot g_i}{\sum_{i=1}^n s_i}$$

Input

There are multiple test cases in a single test file. The first line of the input contains a single integer $T$ ($1 \le T \le 10^4$), indicating the number of test cases.

For each test case:

• The first line contains two positive integers $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), separated by a space, representing the total number of courses and the number of semesters.
• The next $n$ lines each contain three integers $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), separated by spaces, representing the credits, grade points, and the semester in which the course was taken. It is guaranteed that $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \times 10^5$, i.e., $\sum n \le 3 \times 10^5$.

Output

For each test case, output $n - 2m + 1$ lines, with each line corresponding to $k = 2m, k = 2m+1, \dots, k = n$, representing the maximum GPA Xiao Bo can achieve if he only takes the courses from the $1$-st to the $k$-th on his transcript.

Answer Precision Requirement: Your output will be compared with the standard answer. If the contestant's output value is $x$ and the standard answer is $y$, it will be judged as correct if $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Example

Sample 1

2
5 1
9 7 1
1 2 1
9 6 1
6 4 1
4 7 1
9 2
9 1 1
9 9 1
1 9 2
4 4 2
6 10 1
8 6 2
2 7 1
8 6 2
6 5 1

7.0000000000
6.5000000000
6.2631578947
6.3913043478
9.0000000000
9.3750000000
8.3000000000
8.1818181818
7.6470588235
7.2500000000