Описание

Сяо Бо — прилежный студент университета, который очень заботится о своей успеваемости. В каждом семестре он получает зачётные единицы (кредиты) и соответствующие баллы успеваемости за несколько курсов. Баллы успеваемости — это способ оценить результат прохождения курса, а средний взвешенный балл (GPA) является важным показателем общего академического уровня студента. Сяо Бо надеется получить максимально возможный GPA.

В университете действует особое правило: в каждом семестре студенты могут перевести оценку не более чем по одному курсу в режим «Зачёт/Незачёт» (Pass/No Pass, PNP) (разумеется, в каких-то семестрах они могут не переводить в режим PNP ни одного курса). В режиме PNP баллы за этот курс не учитываются при расчёте GPA.

Сяо Бо знает, что за $m$ семестров он прослушал в общей сложности $n$ курсов. Ему известны кредиты, баллы и номер семестра для каждого курса в его ведомости, обозначаемые как $s_i, g_i, t_i$. Гарантируется, что первые $2m$ курсов в ведомости удовлетворяют условию: номер семестра для $i$-го курса равен $\lfloor \frac{i+1}{2} \rfloor$ (это гарантирует, что в каждом семестре изучается хотя бы два курса), тогда как для остальных курсов номер семестра может быть произвольным. Сяо Бо хочет принимать разумные решения в каждом семестре, чтобы максимизировать свой итоговый GPA.

Однако Сяо Бо считает эту задачу слишком простой и хочет узнать: для любого $k$, удовлетворяющего условию $2m \le k \le n$, если он изучит только курсы с $1$-го по $k$-й из своей ведомости, с учётом выбора PNP в каждом семестре, какого максимального GPA он сможет достичь?

Формула расчёта GPA выглядит следующим образом: если в данный момент есть $n$ курсов, для которых не выбран режим PNP, и у $i$-го курса кредиты и баллы равны соответственно $s_i, g_i$, то

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

Входные данные

В одном тестовом файле содержится несколько наборов входных данных. Первая строка входных данных содержит одно целое число $T$ ($1 \le T \le 10^4$), обозначающее количество наборов входных данных.

Для каждого набора входных данных:

• Первая строка содержит два положительных целых числа $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), разделённых пробелом — общее количество курсов и количество семестров.
• Следующие $n$ строк содержат по три целых числа $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), разделённых пробелами — кредиты, баллы и семестр, в котором был прослушан курс. Гарантируется, что $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $3 \times 10^5$, то есть $\sum n \le 3 \times 10^5$.

Выходные данные

Для каждого набора входных данных выведите $n - 2m + 1$ строк, каждая из которых соответствует $k = 2m, k = 2m+1, \dots, k = n$ и представляет максимальный GPA, которого может достичь Сяо Бо, если он прослушает только курсы с $1$-го по $k$-й из своей ведомости.

Требование к точности ответа: Ваш вывод будет сравниваться со стандартным ответом. Если выведенное участником значение равно $x$, а стандартный ответ равен $y$, ответ будет засчитан как правильный, если $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Пример

Пример 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