題目描述

Xiao Bo 是一個勤奮的大學生，非常關心自己的學業成績。在每個學期，他會修讀若干門課程並獲得相應的學分和績點。績點是衡量課程表現的一種方式，而平均學分績點（GPA）是衡量學生整體學術水準的重要指標。Xiao Bo 希望能獲得盡可能高的 GPA。

學校有一項特殊政策：每個學期，學生可以選擇將至多一門課程的成績轉換為「通過/不通過」（PNP）模式（當然，他們也可以選擇在某些學期不將任何課程轉換為 PNP 模式）。在 PNP 模式下，該課程的績點將不計入 GPA 的計算。

Xiao Bo 知道他在 $m$ 個學期中總共修讀了 $n$ 門課程。他知道自己成績單上每門課程的學分、績點和學期，分別記為 $s_i, g_i, t_i$。保證成績單上的前 $2m$ 門課程滿足：第 $i$ 門課程的學期為 $\lfloor \frac{i+1}{2} \rfloor$（這確保了每個學期至少修讀兩門課程），而其餘課程的學期則不作保證。Xiao Bo 希望在每個學期做出合理的決策，以最大化他最終的 GPA。

然而，Xiao Bo 覺得這有點太簡單了，他想知道：對於任何滿足 $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$，表示 Xiao Bo 如果只修讀成績單上第 $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