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$），由空格隔开，分别表示该课程的学分、绩点以及修读该课程的学期。保证对于所有 $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

输出样例 1

7.0000000000
6.5000000000
6.2631578947
6.3913043478
9.0000000000
9.3750000000
8.3000000000
8.1818181818
7.6470588235
7.2500000000