Description

Xiao Bo est un étudiant universitaire assidu qui se soucie beaucoup de ses résultats académiques. À chaque semestre, il obtient des crédits et les points de note correspondants pour plusieurs cours. Les points de note permettent de mesurer la performance dans un cours, tandis que la moyenne pondérée cumulative (GPA) est un indicateur important du niveau académique global d'un étudiant. Xiao Bo espère obtenir le GPA le plus élevé possible.

L'université propose une politique spéciale : à chaque semestre, les étudiants peuvent choisir de convertir la note d'au plus un cours en mode « Réussite/Échec » (Pass/No Pass, PNP) (bien entendu, ils peuvent aussi choisir de ne convertir aucun cours en mode PNP lors de certains semestres). En mode PNP, les points de note de ce cours ne sont pas pris en compte dans le calcul du GPA.

Xiao Bo sait qu'il a suivi un total de $n$ cours sur $m$ semestres. Il connaît les crédits, les points de note et le semestre de chaque cours figurant sur son relevé de notes, notés $s_i, g_i, t_i$. Il est garanti que les $2m$ premiers cours du relevé de notes vérifient : le semestre du $i$-ème cours est $\lfloor \frac{i+1}{2} \rfloor$ (ce qui garantit qu'au moins deux cours sont suivis à chaque semestre), tandis que le semestre des cours restants n'est pas contraint de la sorte. Xiao Bo espère prendre des décisions judicieuses à chaque semestre afin de maximiser son GPA final.

Cependant, Xiao Bo trouve cela un peu trop facile et aimerait savoir : pour tout $k$ vérifiant $2m \le k \le n$, s'il ne suit que les cours allant du $1$-er au $k$-ième sur son relevé de notes, en tenant compte des décisions PNP pour chaque semestre, quel est le GPA maximum qu'il peut atteindre ?

La formule de calcul du GPA est la suivante : en supposant qu'il y ait actuellement $n$ cours n'ayant pas choisi le mode PNP, le $i$-ème cours ayant respectivement $s_i, g_i$ comme crédits et points de note, alors

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

Entrée

Il y a plusieurs cas de test dans un seul fichier de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 10^4$), indiquant le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient deux entiers strictement positifs $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), séparés par un espace, représentant le nombre total de cours et le nombre de semestres.
• Les $n$ lignes suivantes contiennent chacune trois entiers $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), séparés par des espaces, représentant les crédits, les points de note et le semestre au cours duquel le cours a été suivi. Il est garanti que $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $3 \times 10^5$, c'est-à-dire $\sum n \le 3 \times 10^5$.

Sortie

Pour chaque cas de test, affichez $n - 2m + 1$ lignes, chaque ligne correspondant à $k = 2m, k = 2m+1, \dots, k = n$, représentant le GPA maximum que Xiao Bo peut atteindre s'il ne suit que les cours allant du $1$-er au $k$-ième sur son relevé de notes.

Exigence de précision de la réponse : Votre sortie sera comparée à la réponse de référence. Si la valeur affichée par le participant est $x$ et que la réponse de référence est $y$, elle sera jugée correcte si $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Exemple

Exemple 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