Kuvaus

Xiao Bo on ahkera yliopisto-opiskelija, joka on erittäin kiinnostunut opintomenestyksestään. Jokaisella lukukaudella hän ansaitsee opintopisteitä ja vastaavia arvosanapisteitä useista kursseista. Arvosanapisteet ovat tapa mitata kurssisuoritusta, kun taas opintopisteillä painotettu keskiarvo (GPA) on tärkeä opiskelijan yleisen akateemisen tason mittari. Xiao Bo toivoo saavuttavansa mahdollisimman korkean GPA:n.

Yliopistolla on erityiskäytäntö: jokaisella lukukaudella opiskelijat voivat valita muuntavansa enintään yhden kurssin arvosanan ”Hyväksytty/Hylätty” (Pass/No Pass, PNP) -tilaan (toki he voivat myös olla muuntamatta yhtäkään kurssia PNP-tilaan tietyillä lukukausilla). PNP-tilassa kyseisen kurssin arvosanapisteitä ei oteta mukaan GPA:n laskentaan.

Xiao Bo tietää suorittaneensa yhteensä $n$ kurssia $m$ lukukauden aikana. Hän tietää opintosuoritusotteensa jokaisen kurssin opintopisteet, arvosanapisteet ja lukukauden, joita merkitään $s_i, g_i, t_i$. On taattua, että opintosuoritusotteen ensimmäiset $2m$ kurssia täyttävät ehdon: $i$:nnen kurssin lukukausi on $\lfloor \frac{i+1}{2} \rfloor$ (tämä varmistaa, että jokaisella lukukaudella suoritetaan vähintään kaksi kurssia), kun taas loppujen kurssien lukukausista ei ole tällaista taetta. Xiao Bo haluaa tehdä järkeviä päätöksiä jokaisella lukukaudella maksimoidakseen lopullisen GPA:nsa.

Xiao Bo pitää tätä kuitenkin hieman liian helppona ja haluaa tietää: mille tahansa luvulle $k$, jolle $2m \le k \le n$, jos hän suorittaa vain opintosuoritusotteensa kurssit $1$:sestä $k$:nteen, ottaen huomioon kunkin lukukauden PNP-päätökset, mikä on suurin GPA, jonka hän voi saavuttaa?

GPA:n laskukaava on seuraava: olettaen, että tällä hetkellä on $n$ kurssia, joille ei ole valittu PNP-tilaa, ja $i$:nnen kurssin opintopisteet ja arvosanapisteet ovat $s_i, g_i$, niin

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

Syöte

Yhdessä testitiedostossa on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa:

• Ensimmäinen rivi sisältää kaksi positiivista kokonaislukua $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$) välilyönnillä erotettuina, jotka kuvaavat kurssien kokonaismäärää ja lukukausien lukumäärää.
• Seuraavat $n$ riviä sisältävät kukin kolme välilyönnein erotettua kokonaislukua $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), jotka kuvaavat opintopisteitä, arvosanapisteitä ja lukukautta, jolloin kurssi suoritettiin. On taattua, että $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

On taattua, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $3 \times 10^5$, eli $\sum n \le 3 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle $n - 2m + 1$ riviä, joista kukin vastaa arvoa $k = 2m, k = 2m+1, \dots, k = n$ ja kuvaa suurinta GPA:ta, jonka Xiao Bo voi saavuttaa, jos hän suorittaa vain kurssit $1$:sestä $k$:nteen opintosuoritusotteeltaan.

Tarkkuusvaatimus: Tulostettasi verrataan mallivastaukseen. Jos kilpailijan tulostama arvo on $x$ ja mallivastaus on $y$, vastaus hyväksytään, jos $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Esimerkki

Esimerkki 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