문제 설명
Xiao Bo는 자신의 학업 성적에 매우 관심이 많은 성실한 대학생입니다. 매 학기 그는 여러 과목을 수강하고 그에 해당하는 학점(단위수)과 평점을 받습니다. 평점은 과목 성취도를 측정하는 방법이며, 평점 평균(GPA)은 학생의 전반적인 학업 수준을 나타내는 중요한 지표입니다. Xiao Bo는 가능한 한 가장 높은 GPA를 얻기를 희망합니다.
학교에는 특별한 제도가 있습니다: 매 학기 학생들은 최대 한 과목의 성적을 "급제/낙제"(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$임을 만족함이 보장되며(이는 매 학기 적어도 두 과목 이상 수강함을 보장합니다), 나머지 과목들의 학기는 따로 보장되지 않습니다. 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}$$
입력
하나의 테스트 파일에 여러 개의 테스트 케이스가 주어집니다. 입력의 첫째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 $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$임이 보장됩니다.
출력
각 테스트 케이스마다 $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 17.0000000000
6.5000000000
6.2631578947
6.3913043478
9.0000000000
9.3750000000
8.3000000000
8.1818181818
7.6470588235
7.2500000000