Lýsing

Xiao Bo er duglegur háskólanemi sem er mjög annt um námsárangur sinn. Á hverri önn vinnur hann sér inn einingar og samsvarandi einkunnastig fyrir nokkur námskeið. Einkunnastig eru leið til að mæla frammistöðu í námskeiði, en vegið meðaltal einkunna (GPA) er mikilvægur mælikvarði á heildarnámsstöðu nemanda. Xiao Bo vonast til að ná sem hæstu GPA.

Skólinn býður upp á sérstaka reglu: á hverri önn geta nemendur valið að breyta einkunn í að hámarki einu námskeiði í „Staðið/Fallið“ (Pass/No Pass, PNP) ham (auðvitað geta þeir líka valið að breyta engu námskeiði í PNP-ham á tilteknum önnum). Í PNP-ham eru einkunnastig þess námskeiðs ekki tekin með í útreikningi á GPA.

Xiao Bo veit að hann hefur tekið alls $n$ námskeið á $m$ önnum. Hann þekkir einingarnar, einkunnastigin og önnina fyrir hvert námskeið á námsferilsyfirliti sínu, táknað sem $s_i, g_i, t_i$. Tryggt er að fyrstu $2m$ námskeiðin á yfirlitinu uppfylli: önnin fyrir $i$-ta námskeiðið er $\lfloor \frac{i+1}{2} \rfloor$ (þetta tryggir að tekin séu að minnsta kosti tvö námskeið á hverri önn), en önnin fyrir afganginn af námskeiðunum er ekki bundin slíkum skilyrðum. Xiao Bo vonast til að taka skynsamlegar ákvarðanir á hverri önn til að hámarka loka-GPA sitt.

Hins vegar finnst Xiao Bo þetta aðeins of auðvelt og vill vita: fyrir sérhvert $k$ sem uppfyllir $2m \le k \le n$, ef hann tekur aðeins námskeiðin frá því $1$-sta til þess $k$-ta á yfirlitinu sínu, með tilliti til PNP-ákvarðana fyrir hverja önn, hvert er hæsta GPA sem hann getur náð?

Formúlan fyrir útreikning á GPA er eftirfarandi: ef gert er ráð fyrir að nú séu $n$ námskeið sem hafa ekki valið PNP-ham, þar sem $i$-ta námskeiðið hefur einingar og einkunnastig $s_i, g_i$, í sömu röð, þá er

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

Inntak

Það eru mörg prófunartilfelli í einni prófunarskrá. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^4$), sem gefur til kynna fjölda prófunartilfella.

Fyrir hvert prófunartilfelli:

• Fyrsta línan inniheldur tvær jákvæðar heiltölur $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), aðskildar með bili, sem tákna heildarfjölda námskeiða og fjölda anna.
• Næstu $n$ línur innihalda hver um sig þrjár heiltölur $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), aðskildar með bilum, sem tákna einingar, einkunnastig og önnina sem námskeiðið var tekið á. Tryggt er að $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Tryggt er að summa $n$ yfir öll prófunartilfelli fari ekki yfir $3 \times 10^5$, þ.e. $\sum n \le 3 \times 10^5$.

Úttak

Fyrir hvert prófunartilfelli skal prenta $n - 2m + 1$ línur, þar sem hver lína samsvarar $k = 2m, k = 2m+1, \dots, k = n$, og táknar hæsta GPA sem Xiao Bo getur náð ef hann tekur aðeins námskeiðin frá því $1$-sta til þess $k$-ta á námsferilsyfirliti sínu.

Nákvæmniskrafa svars: Úttakið þitt verður borið saman við staðalsvarið. Ef úttaksgildi keppandans er $x$ og staðalsvarið er $y$, verður það dæmt rétt ef $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Dæmi

Dæmi 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