題目描述

小博係一個勤奮嘅大學生，非常關心自己嘅學業成績。喺每個學期，佢會修讀若干門課程並獲得相應嘅學分同績點。績點係衡量課程表現嘅一種方式，而平均學分績點（GPA）係衡量學生整體學術水平嘅重要指標。小博希望能夠獲得盡可能高嘅 GPA。

學校有一項特殊政策：每個學期，學生可以選擇將最多一門課程嘅成績轉換為「合格/唔合格」（PNP）模式（當然，佢哋亦都可以選擇喺某啲學期唔將任何課程轉換為 PNP 模式）。喺 PNP 模式下，呢門課程嘅績點將唔會計入 GPA 嘅計算。

小博知道佢喺 $m$ 個學期入面總共修讀咗 $n$ 門課程。佢知道自己成績表上面每門課程嘅學分、績點同學期，分別記為 $s_i, g_i, t_i$。題目保證成績表上面嘅前 $2m$ 門課程滿足：第 $i$ 門課程嘅學期係 $\lfloor \frac{i+1}{2} \rfloor$（呢個確保咗每個學期至少修讀兩門課程），而其餘課程嘅學期就唔作保證。小博希望喺每個學期做出合理嘅決策，以最大化佢最終嘅 GPA。

不過，小博覺得呢個有啲太簡單，佢想知道：對於任何滿足 $2m \le k \le n$ 嘅 $k$，如果佢只修讀成績表上面第 $1$ 到第 $k$ 門課程，喺考慮每個學期嘅 PNP 決策之後，佢能夠達到嘅最大 GPA 係幾多？

GPA 嘅計算公式如下：假設目前有 $n$ 門課程冇選擇 PNP 模式，而且第 $i$ 門課程嘅學分同績點分別係 $s_i, g_i$，咁：

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

輸入格式

單個測試文件包含多組測試數據。輸入嘅第一行包含一個整數 $T$（$1 \le T \le 10^4$），代表測試數據嘅組數。

對於每組測試數據：

• 第一行包含兩個正整數 $n, m$（$1 \le m \le 8, 2m \le n \le 10^5$），用空格隔開，分別代表課程總數同學期數。
• 接住落嚟嘅 $n$ 行，每行包含三個整數 $s_i, g_i, t_i$（$1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$），用空格隔開，分別代表嗰門課程嘅學分、績點以及修讀嗰門課程嘅學期。保證 $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$。

題目保證所有測試數據入面 $n$ 嘅總和唔超過 $3 \times 10^5$，即係 $\sum n \le 3 \times 10^5$。

輸出格式

對於每組測試數據，輸出 $n - 2m + 1$ 行，每行分別對應 $k = 2m, k = 2m+1, \dots, k = n$，代表小博如果只修讀成績表上面第 $1$ 到第 $k$ 門課程嗰陣，所能夠達到嘅最大 GPA。

答案精度要求：你嘅輸出將會同標準答案進行比對。如果選手嘅輸出值係 $x$，標準答案係 $y$，當滿足 $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$ 嗰陣，將會被判定為正確。

樣例

樣例 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