Опис

Сяо Бо — старанний студент університету, який дуже переймається своєю академічною успішністю. У кожному семестрі він отримує кредити та відповідні бали успішності за декілька курсів. Бали успішності — це спосіб виміряти результати проходження курсу, а середній ваговий бал (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