Beskrivning

Xiao Bo är en flitig högskolestudent som bryr sig mycket om sina studieresultat. Varje termin tjänar han in högskolepoäng och motsvarande betygspoäng för flera kurser. Betygspoäng är ett sätt att mäta prestationen i en kurs, medan medelbetyget (GPA) är en viktig indikator på en students övergripande akademiska nivå. Xiao Bo hoppas kunna uppnå högsta möjliga GPA.

Skolan erbjuder en särskild policy: varje termin kan studenterna välja att omvandla betyget i högst en kurs till läget ”Godkänd/Underkänd” (Pass/No Pass, PNP) (naturligtvis kan de också välja att inte omvandla någon kurs till PNP-läge under vissa terminer). I PNP-läge räknas betygspoängen för denna kurs inte med i GPA-beräkningen.

Xiao Bo vet att han har läst totalt $n$ kurser under $m$ terminer. Han känner till poängen, betygspoängen och terminen för varje kurs på sitt studieintyg, betecknade som $s_i, g_i, t_i$. Det garanteras att de första $2m$ kurserna på studieintyget uppfyller följande: terminen för den $i$:te kursen är $\lfloor \frac{i+1}{2} \rfloor$ (detta säkerställer att minst två kurser läses varje termin), medan terminen för de återstående kurserna inte har denna garanti. Xiao Bo hoppas kunna fatta kloka beslut varje termin för att maximera sitt slutliga GPA.

Xiao Bo tycker dock att detta är lite för enkelt och vill veta: för varje $k$ som uppfyller $2m \le k \le n$, om han bara läser kurserna från den $1$:a till den $k$:te på sitt studieintyg, med hänsyn till PNP-besluten för varje termin, vilket är det maximala GPA han kan uppnå?

Formeln för GPA-beräkning är följande: om vi antar att det för närvarande finns $n$ kurser som inte har valt PNP-läge, där den $i$:te kursen har poäng respektive betygspoäng $s_i, g_i$, så gäller

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

Indata

Det finns flera testfall i en enda testfil. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T \le 10^4$), vilket anger antalet testfall.

För varje testfall:

• Den första raden innehåller två positiva heltal $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), åtskilda av ett mellanslag, vilka representerar det totala antalet kurser och antalet terminer.
• De följande $n$ raderna innehåller var och en tre heltal $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), åtskilda av mellanslag, vilka representerar poängen, betygspoängen och terminen då kursen lästes. Det garanteras att $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $3 \times 10^5$, dvs. $\sum n \le 3 \times 10^5$.

Utdata

För varje testfall, skriv ut $n - 2m + 1$ rader, där varje rad motsvarar $k = 2m, k = 2m+1, \dots, k = n$, och representerar det maximala GPA Xiao Bo kan uppnå om han bara läser kurserna från den $1$:a till den $k$:te på sitt studieintyg.

Precisionskrav för svaret: Din utdata kommer att jämföras med standardsvar. Om tävlingsdeltagarens utdatavärde är $x$ och standardsvar är $y$, bedöms det som korrekt om $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Exempel

Exempel 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