Beschreibung

Xiao Bo ist ein fleißiger Student, dem seine akademischen Leistungen sehr wichtig sind. In jedem Semester erwirbt er für mehrere Kurse Leistungspunkte (Credits) und entsprechende Notenpunkte. Notenpunkte sind ein Maß für die Kursleistung, während der Notendurchschnitt (GPA) ein wichtiger Indikator für das akademische Gesamtniveau eines Studenten ist. Xiao Bo hofft, einen möglichst hohen GPA zu erreichen.

Die Hochschule bietet eine Sonderregelung an: In jedem Semester können Studenten wählen, die Bewertung von höchstens einem Kurs in den Modus „Bestanden/Nicht bestanden“ (Pass/No Pass, PNP) umzuwandeln (natürlich können sie sich in bestimmten Semestern auch dafür entscheiden, keinen Kurs in den PNP-Modus umzuwandeln). Im PNP-Modus fließen die Notenpunkte dieses Kurses nicht in die GPA-Berechnung ein.

Xiao Bo weiß, dass er über $m$ Semester hinweg insgesamt $n$ Kurse belegt hat. Er kennt die Credits, die Notenpunkte und das Semester für jeden Kurs auf seiner Leistungsübersicht, bezeichnet mit $s_i, g_i, t_i$. Es wird garantiert, dass die ersten $2m$ Kurse auf der Leistungsübersicht Folgendes erfüllen: Das Semester für den $i$-ten Kurs ist $\lfloor \frac{i+1}{2} \rfloor$ (dies stellt sicher, dass in jedem Semester mindestens zwei Kurse belegt werden), während das Semester für die übrigen Kurse nicht weiter eingeschränkt ist. Xiao Bo möchte in jedem Semester kluge Entscheidungen treffen, um seinen endgültigen GPA zu maximieren.

Allerdings findet Xiao Bo das etwas zu einfach und möchte wissen: Für jedes $k$ mit $2m \le k \le n$, wenn er nur die Kurse vom $1$-ten bis zum $k$-ten auf seiner Leistungsübersicht belegt und die PNP-Entscheidungen für jedes Semester berücksichtigt, was ist der maximale GPA, den er erreichen kann?

Die Formel zur Berechnung des GPA lautet wie folgt: Angenommen, es gibt derzeit $n$ Kurse, für die nicht der PNP-Modus gewählt wurde, wobei der $i$-te Kurs Credits und Notenpunkte von $s_i, g_i$ hat, dann gilt:

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

Eingabe

Es gibt mehrere Testfälle in einer einzigen Testdatei. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt.

Für jeden Testfall gilt:

• Die erste Zeile enthält zwei positive ganze Zahlen $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), getrennt durch ein Leerzeichen, die die Gesamtzahl der Kurse und die Anzahl der Semester darstellen.
• Die nächsten $n$ Zeilen enthalten jeweils drei durch Leerzeichen getrennte ganze Zahlen $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), die die Credits, die Notenpunkte und das Semester darstellen, in dem der Kurs belegt wurde. Es wird garantiert, dass $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$ gilt.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $3 \times 10^5$ nicht überschreitet, d. h. $\sum n \le 3 \times 10^5$.

Ausgabe

Gib für jeden Testfall $n - 2m + 1$ Zeilen aus, wobei jede Zeile $k = 2m, k = 2m+1, \dots, k = n$ entspricht und den maximalen GPA darstellt, den Xiao Bo erreichen kann, wenn er nur die Kurse vom $1$-ten bis zum $k$-ten auf seiner Leistungsübersicht belegt.

Genauigkeitsanforderung: Deine Ausgabe wird mit der Standardlösung verglichen. Wenn der Ausgabewert des Teilnehmers $x$ und die Standardlösung $y$ ist, wird die Antwort als korrekt gewertet, falls $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$ gilt.

Beispiel

Beispiel 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