問題文

Xiao Bo は学業成績を非常に気にかけている勤勉な大学生です。各学期において、彼はいくつかの講義を履修し、対応する単位数とグレードポイント（GP）を取得します。グレードポイントは講義の成績を測る指標であり、グレードポイント平均（GPA）は学生の総合的な学力水準を示す重要な指標です。Xiao Bo は可能な限り高い GPA を達成したいと考えています。

大学には特別な制度があります。各学期において、学生は高々 1 つの講義の成績を「合否判定のみ」（Pass/No Pass, PNP）モードに変換することを選択できます（もちろん、ある学期においてどの講義も PNP モードに変換しないことを選択することもできます）。PNP モードにした講義のグレードポイントは、GPA の計算に含まれません。

Xiao Bo は $m$ 学期にわたって合計 $n$ 個の講義を履修したことを知っています。彼は成績証明書に記載された各講義の単位数、グレードポイント、および履修学期を把握しており、それぞれ $s_i, g_i, t_i$ と表されます。成績証明書の最初の $2m$ 個の講義については、$i$ 番目の講義の学期が $\lfloor \frac{i+1}{2} \rfloor$ を満たすことが保証されています（これにより、各学期に少なくとも 2 つの講義が履修されることが保証されます）。一方、残りの講義の学期についてはこのような保証はありません。Xiao Bo は最終的な GPA を最大化するために、各学期で適切な選択を行いたいと考えています。

しかし、Xiao Bo はこれだけでは少し簡単すぎると思い、次のことを知りたいと考えました：$2m \le k \le n$ を満たす任意の $k$ について、もし成績証明書の $1$ 番目から $k$ 番目までの講義のみを履修したとし、各学期の PNP の選択を考慮した場合、達成できる最大の GPA はいくつになるでしょうか？

GPA の計算式は以下の通りです。現在 PNP モードを選択していない講義が $n$ 個あり、$i$ 番目の講義の単位数とグレードポイントがそれぞれ $s_i, g_i$ であるとすると、

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

入力

1 つのテストファイルに複数のテストケースが含まれます。入力の最初の行には、テストケースの個数を表す単一の整数 $T$ ($1 \le T \le 10^4$) が与えられます。

各テストケースについて：

• 最初の行には、空白で区切られた 2 つの正の整数 $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$) が与えられ、それぞれ講義の総数と学期数を表します。
• 続く $n$ 行には、それぞれ空白で区切られた 3 つの整数 $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$ が保証されます。

出力

各テストケースについて、$k = 2m, k = 2m+1, \dots, k = n$ にそれぞれ対応する $n - 2m + 1$ 行を出力してください。各行は、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