Descripción

Xiao Bo es un estudiante universitario diligente que se preocupa mucho por su rendimiento académico. En cada semestre, obtiene créditos y los puntos de calificación correspondientes por varios cursos. Los puntos de calificación son una forma de medir el desempeño en un curso, mientras que el promedio de calificaciones (GPA) es un indicador importante del nivel académico general de un estudiante. Xiao Bo espera lograr el GPA más alto posible.

La universidad ofrece una política especial: cada semestre, los estudiantes pueden elegir convertir la calificación de a lo sumo un curso a la modalidad «Aprobado/No aprobado» (Pass/No Pass, PNP) (por supuesto, también pueden optar por no convertir ningún curso a la modalidad PNP en ciertos semestres). En la modalidad PNP, los puntos de calificación de dicho curso no se incluirán en el cálculo del GPA.

Xiao Bo sabe que ha cursado un total de $n$ cursos a lo largo de $m$ semestres. Conoce los créditos, los puntos de calificación y el semestre de cada curso en su expediente académico, denotados como $s_i, g_i, t_i$. Se garantiza que los primeros $2m$ cursos del expediente satisfacen: el semestre para el $i$-ésimo curso es $\lfloor \frac{i+1}{2} \rfloor$ (esto asegura que se tomen al menos dos cursos cada semestre), mientras que el semestre para los cursos restantes no tiene esta garantía. Xiao Bo espera tomar decisiones razonables cada semestre para maximizar su GPA final.

Sin embargo, Xiao Bo piensa que esto es un poco demasiado fácil y quiere saber: para cualquier $k$ que satisfaga $2m \le k \le n$, si solo toma los cursos desde el $1$-ro hasta el $k$-ésimo en su expediente, considerando las decisiones PNP para cada semestre, ¿cuál es el GPA máximo que puede lograr?

La fórmula de cálculo del GPA es la siguiente: suponiendo que actualmente hay $n$ cursos que no han elegido la modalidad PNP, donde el $i$-ésimo curso tiene créditos y puntos de calificación $s_i, g_i$, respectivamente, entonces

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

Entrada

Hay múltiples casos de prueba en un solo archivo de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T \le 10^4$), que indica el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene dos enteros positivos $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), separados por un espacio, que representan el número total de cursos y el número de semestres.
• Las siguientes $n$ líneas contienen cada una tres enteros $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), separados por espacios, que representan los créditos, los puntos de calificación y el semestre en el que se tomó el curso. Se garantiza que $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $3 \times 10^5$, es decir, $\sum n \le 3 \times 10^5$.

Salida

Para cada caso de prueba, imprime $n - 2m + 1$ líneas, donde cada línea corresponde a $k = 2m, k = 2m+1, \dots, k = n$, representando el GPA máximo que Xiao Bo puede lograr si solo toma los cursos desde el $1$-ro hasta el $k$-ésimo en su expediente.

Requisito de precisión de la respuesta: Tu salida se comparará con la respuesta estándar. Si el valor de salida del concursante es $x$ y la respuesta estándar es $y$, se juzgará como correcto si $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Ejemplo

Ejemplo 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