Mô tả bài toán

Xiao Bo là một sinh viên đại học chăm chỉ và rất quan tâm đến kết quả học tập của mình. Trong mỗi học kỳ, cậu tích lũy số tín chỉ và điểm số tương ứng cho một số môn học. Điểm môn học là cách đo lường kết quả của môn học đó, trong khi điểm trung bình tích lũy (GPA) là một chỉ số quan trọng phản ánh trình độ học tập tổng thể của sinh viên. Xiao Bo hy vọng đạt được mức GPA cao nhất có thể.

Nhà trường có một chính sách đặc biệt: mỗi học kỳ, sinh viên có thể chọn chuyển đổi điểm của nhiều nhất một môn học sang chế độ "Đạt/Không Đạt" (Pass/No Pass - PNP) (tất nhiên, họ cũng có thể chọn không chuyển đổi môn học nào sang chế độ PNP trong một số học kỳ nhất định). Ở chế độ PNP, điểm của môn học này sẽ không được tính vào công thức tính GPA.

Xiao Bo biết rằng cậu đã học tổng cộng $n$ môn học trong $m$ học kỳ. Cậu biết rõ số tín chỉ, điểm số và học kỳ của từng môn học trên bảng điểm của mình, lần lượt ký hiệu là $s_i, g_i, t_i$. Đảm bảo rằng $2m$ môn học đầu tiên trên bảng điểm thỏa mãn: học kỳ của môn học thứ $i$ là $\lfloor \frac{i+1}{2} \rfloor$ (điều này đảm bảo mỗi học kỳ có ít nhất hai môn học được học), trong khi học kỳ của các môn học còn lại thì không có ràng buộc này. Xiao Bo hy vọng sẽ đưa ra các quyết định hợp lý trong mỗi học kỳ để tối đa hóa GPA cuối cùng của mình.

Tuy nhiên, Xiao Bo cho rằng bài toán này hơi quá dễ và muốn biết: với mọi $k$ thỏa mãn $2m \le k \le n$, nếu cậu chỉ học các môn từ thứ $1$ đến thứ $k$ trên bảng điểm, xét các quyết định PNP cho từng học kỳ, thì mức GPA tối đa mà cậu có thể đạt được là bao nhiêu?

Công thức tính GPA như sau: giả sử hiện tại có $n$ môn học không chọn chế độ PNP, với môn học thứ $i$ có số tín chỉ và điểm số lần lượt là $s_i, g_i$, khi đó:

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

Dữ liệu vào

Có nhiều bộ test trong một tệp dữ liệu vào. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^4$), cho biết số lượng bộ test.

Với mỗi bộ test:

• Dòng đầu tiên chứa hai số nguyên dương $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), cách nhau bởi dấu cách, lần lượt biểu thị tổng số môn học và số học kỳ.
• $n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), cách nhau bởi dấu cách, lần lượt biểu thị số tín chỉ, điểm số và học kỳ mà môn học đó được học. Đảm bảo rằng $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ test không vượt quá $3 \times 10^5$, tức là $\sum n \le 3 \times 10^5$.

Dữ liệu ra

Với mỗi bộ test, in ra $n - 2m + 1$ dòng, mỗi dòng tương ứng với $k = 2m, k = 2m+1, \dots, k = n$, biểu thị mức GPA tối đa mà Xiao Bo có thể đạt được nếu cậu chỉ học các môn từ thứ $1$ đến thứ $k$ trên bảng điểm.

Yêu cầu độ chính xác: Kết quả của bạn sẽ được so sánh với đáp án chuẩn. Nếu giá trị in ra của thí sinh là $x$ và đáp án chuẩn là $y$, kết quả sẽ được coi là đúng nếu $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Ví dụ

Ví dụ 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