Beskrivelse

Xiao Bo er en flittig universitetsstudent som er svært opptatt av sine akademiske prestasjoner. Hvert semester tjener han studiepoeng og tilhørende karakterpoeng for flere emner. Karakterpoeng er en måte å måle prestasjonen i et emne på, mens karaktersnittet (GPA) er en viktig indikator på en students generelle akademiske nivå. Xiao Bo håper å oppnå høyest mulig GPA.

Universitetet tilbyr en spesiell ordning: hvert semester kan studentene velge å gjøre om karakteren i høyst ett emne til «Bestått/Ikke bestått»-modus (Pass/No Pass, PNP) (selvfølgelig kan de også velge å ikke gjøre om noen emner til PNP-modus i enkelte semestre). I PNP-modus vil ikke karakterpoengene for dette emnet inkluderes i GPA-beregningen.

Xiao Bo vet at han har tatt totalt $n$ emner over $m$ semestre. Han kjenner studiepoengene, karakterpoengene og semesteret for hvert emne på karakterutskriften sin, betegnet som $s_i, g_i, t_i$. Det er garantert at de første $2m$ emnene på karakterutskriften oppfyller følgende: semesteret for det $i$-te emnet er $\lfloor \frac{i+1}{2} \rfloor$ (dette sikrer at minst to emner tas hvert semester), mens semesteret for de resterende emnene ikke er garantert. Xiao Bo håper å ta fornuftige valg hvert semester for å maksimere sin endelige GPA.

Xiao Bo synes imidlertid at dette er litt for enkelt, og vil vite: for enhver $k$ som oppfyller $2m \le k \le n$, hvis han bare tar emnene fra det $1$-ste til det $k$-te på karakterutskriften sin, tatt i betraktning PNP-valgene for hvert semester, hva er den maksimale GPA-en han kan oppnå?

Formelen for GPA-beregning er som følger: forutsatt at det for øyeblikket er $n$ emner som ikke har valgt PNP-modus, der det $i$-te emnet har henholdsvis studiepoeng og karakterpoeng $s_i, g_i$, så er

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

Inndata

Det er flere testtilfeller i én enkelt testfil. Den første linjen av inndataene inneholder et enkelt heltall $T$ ($1 \le T \le 10^4$), som angir antallet testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder to positive heltall $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), atskilt med et mellomrom, som representerer det totale antallet emner og antallet semestre.
• De neste $n$ linjene inneholder hver tre heltall $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), atskilt med mellomrom, som representerer studiepoengene, karakterpoengene og semesteret da emnet ble tatt. Det er garantert at $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $3 \times 10^5$, dvs. $\sum n \le 3 \times 10^5$.

Utdata

For hvert testtilfelle, skriv ut $n - 2m + 1$ linjer, der hver linje tilsvarer $k = 2m, k = 2m+1, \dots, k = n$, og representerer den maksimale GPA-en Xiao Bo kan oppnå hvis han bare tar emnene fra det $1$-ste til det $k$-te på karakterutskriften sin.

Presisjonskrav for svaret: Utdataene dine vil bli sammenlignet med fasitsvaret. Hvis deltakerens utdataverdi er $x$ og fasitsvaret er $y$, vil det bli bedømt som riktig hvis $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Eksempel

Eksempel 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