Descrizione

Xiao Bo è uno studente universitario diligente che tiene molto al proprio rendimento accademico. In ogni semestre, ottiene crediti e i corrispondenti punti di voto per diversi corsi. I punti di voto sono un modo per misurare il rendimento in un corso, mentre la media ponderata dei voti (GPA) è un indicatore importante del livello accademico complessivo di uno studente. Xiao Bo spera di ottenere il GPA più alto possibile.

L'università offre una politica speciale: ogni semestre, gli studenti possono scegliere di convertire il voto di al massimo un corso nella modalità "Idoneo/Non idoneo" (Pass/No Pass, PNP) (naturalmente, possono anche scegliere di non convertire alcun corso in modalità PNP in determinati semestri). In modalità PNP, i punti di voto di tale corso non verranno inclusi nel calcolo del GPA.

Xiao Bo sa di aver seguito un totale di $n$ corsi nell'arco di $m$ semestri. Conosce i crediti, i punti di voto e il semestre di ciascun corso sul suo libretto, indicati con $s_i, g_i, t_i$. È garantito che i primi $2m$ corsi sul libretto soddisfino la seguente proprietà: il semestre per l'$i$-esimo corso è $\lfloor \frac{i+1}{2} \rfloor$ (questo assicura che vengano seguiti almeno due corsi in ogni semestre), mentre il semestre per i corsi rimanenti non ha tale vincolo. Xiao Bo spera di prendere decisioni oculate in ogni semestre per massimizzare il suo GPA finale.

Tuttavia, Xiao Bo pensa che questo sia un po' troppo facile e vuole sapere: per ogni $k$ che soddisfa $2m \le k \le n$, se segue solo i corsi dal $1$-o al $k$-esimo sul suo libretto, considerando le decisioni PNP per ciascun semestre, qual è il GPA massimo che può ottenere?

La formula per il calcolo del GPA è la seguente: supponendo che ci siano attualmente $n$ corsi per i quali non è stata scelta la modalità PNP, dove l'$i$-esimo corso ha crediti e punti di voto rispettivamente pari a $s_i, g_i$, allora

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

Input

Ci sono più casi di test in un singolo file di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test.

Per ciascun caso di test:

• La prima riga contiene due interi positivi $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), separati da uno spazio, che rappresentano il numero totale di corsi e il numero di semestri.
• Le successive $n$ righe contengono ciascuna tre interi $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), separati da spazi, che rappresentano i crediti, i punti di voto e il semestre in cui è stato seguito il corso. È garantito che $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

È garantito che la somma di $n$ su tutti i casi di test non superi $3 \times 10^5$, ovvero $\sum n \le 3 \times 10^5$.

Output

Per ciascun caso di test, stampa $n - 2m + 1$ righe, in cui ogni riga corrisponde a $k = 2m, k = 2m+1, \dots, k = n$, e rappresenta il GPA massimo che Xiao Bo può ottenere se segue solo i corsi dal $1$-o al $k$-esimo sul suo libretto.

Requisito di precisione della risposta: Il tuo output verrà confrontato con la risposta corretta. Se il valore stampato dal concorrente è $x$ e la risposta corretta è $y$, verrà giudicato corretto se $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Esempio

Esempio 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