Opis problemu

Xiao Bo jest pilnym studentem, któremu bardzo zależy na wynikach w nauce. W każdym semestrze zdobywa punkty ECTS (kredyty) oraz odpowiadające im punkty ocen za kilka przedmiotów. Punkty ocen służą do mierzenia wyników z danego przedmiotu, natomiast średnia ważona ocen (GPA) jest ważnym wskaźnikiem ogólnego poziomu akademickiego studenta. Xiao Bo chciałby osiągnąć jak najwyższe GPA.

Uczelnia oferuje specjalną zasadę: w każdym semestrze studenci mogą zamienić ocenę z co najwyżej jednego przedmiotu na tryb „Zaliczone/Niezaliczone” (Pass/No Pass, PNP) (oczywiście w niektórych semestrach mogą też nie zamieniać żadnego przedmiotu na tryb PNP). W trybie PNP punkty ocen z tego przedmiotu nie są uwzględniane przy obliczaniu GPA.

Xiao Bo wie, że w ciągu $m$ semestrów odbył łącznie $n$ przedmiotów. Zna liczbę punktów kredytowych, punkty ocen oraz semestr dla każdego przedmiotu w swoim wykazie ocen, oznaczane jako $s_i, g_i, t_i$. Gwarantuje się, że pierwsze $2m$ przedmiotów w wykazie spełnia warunek: semestr dla $i$-tego przedmiotu wynosi $\lfloor \frac{i+1}{2} \rfloor$ (co zapewnia, że w każdym semestrze realizowane są co najmniej dwa przedmioty), natomiast semestr dla pozostałych przedmiotów może być dowolny. Xiao Bo chce podejmować racjonalne decyzje w każdym semestrze, aby zmaksymalizować swoje końcowe GPA.

Jednak Xiao Bo uważa, że to trochę za proste, i chciałby wiedzieć: dla dowolnego $k$ spełniającego $2m \le k \le n$, gdyby zrealizował tylko przedmioty od $1$-szego do $k$-tego ze swojego wykazu ocen, uwzględniając decyzje o PNP w każdym semestrze, jakie maksymalne GPA może osiągnąć?

Wzór na obliczenie GPA jest następujący: zakładając, że obecnie jest $n$ przedmiotów, dla których nie wybrano trybu PNP, a $i$-ty przedmiot ma odpowiednio liczbę punktów kredytowych oraz punkty ocen równe $s_i, g_i$, wówczas

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

Wejście

W jednym pliku testowym znajduje się wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), oddzielone spacją, oznaczające łączną liczbę przedmiotów oraz liczbę semestrów.
• Kolejne $n$ wierszy zawiera po trzy liczby całkowite $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), oddzielone spacjami, oznaczające punkty kredytowe, punkty ocen oraz semestr, w którym realizowano dany przedmiot. Gwarantuje się, że $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $3 \times 10^5$, tzn. $\sum n \le 3 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz $n - 2m + 1$ wierszy, gdzie kolejne wiersze odpowiadają $k = 2m, k = 2m+1, \dots, k = n$ i oznaczają maksymalne GPA, jakie Xiao Bo może osiągnąć, biorąc pod uwagę tylko przedmioty od $1$-szego do $k$-tego ze swojego wykazu ocen.

Wymagania dotyczące dokładności odpowiedzi: Twoje wyjście zostanie porównane z odpowiedzią wzorcową. Jeśli wartość wypisana przez zawodnika wynosi $x$, a odpowiedź wzorcowa to $y$, odpowiedź zostanie uznana za poprawną, gdy $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Przykład

Przykład 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