Deskripsi

Xiao Bo adalah seorang mahasiswa rajin yang sangat peduli dengan prestasi akademiknya. Pada setiap semester, ia memperoleh satuan kredit dan poin nilai yang sesuai untuk beberapa mata kuliah. Poin nilai adalah cara untuk mengukur performa mata kuliah, sedangkan indeks prestasi kumulatif (GPA) adalah indikator penting dari tingkat akademik mahasiswa secara keseluruhan. Xiao Bo berharap dapat mencapai GPA setinggi mungkin.

Pihak kampus menawarkan kebijakan khusus: setiap semester, mahasiswa dapat memilih untuk mengubah nilai dari paling banyak satu mata kuliah menjadi mode "Lulus/Tidak Lulus" (Pass/No Pass - PNP) (tentu saja, mereka juga dapat memilih untuk tidak mengubah mata kuliah apa pun ke mode PNP pada semester tertentu). Dalam mode PNP, poin nilai dari mata kuliah tersebut tidak akan disertakan dalam perhitungan GPA.

Xiao Bo mengetahui bahwa ia telah mengambil total $n$ mata kuliah selama $m$ semester. Ia mengetahui satuan kredit, poin nilai, dan semester untuk setiap mata kuliah pada transkrip nilainya, yang dinyatakan sebagai $s_i, g_i, t_i$. Dijamin bahwa $2m$ mata kuliah pertama pada transkrip memenuhi: semester untuk mata kuliah ke-$i$ adalah $\lfloor \frac{i+1}{2} \rfloor$ (ini memastikan bahwa setidaknya dua mata kuliah diambil pada setiap semester), sedangkan semester untuk mata kuliah sisanya tidak dijamin demikian. Xiao Bo berharap dapat membuat keputusan yang tepat pada setiap semester untuk memaksimalkan GPA akhirnya.

Namun, Xiao Bo merasa bahwa hal ini sedikit terlalu mudah dan ingin mengetahui: untuk setiap $k$ yang memenuhi $2m \le k \le n$, jika ia hanya mengambil mata kuliah dari urutan ke-$1$ hingga ke-$k$ pada transkripnya, dengan mempertimbangkan keputusan PNP untuk setiap semester, berapakah GPA maksimum yang dapat ia capai?

Rumus perhitungan GPA adalah sebagai berikut: dengan mengasumsikan saat ini terdapat $n$ mata kuliah yang tidak memilih mode PNP, dengan mata kuliah ke-$i$ memiliki satuan kredit dan poin nilai masing-masing $s_i, g_i$, maka

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

Masukan

Terdapat beberapa kasus uji dalam satu berkas uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji:

• Baris pertama berisi dua bilangan bulat positif $n, m$ ($1 \le m \le 8, 2m \le n \le 10^5$), dipisahkan oleh spasi, yang menyatakan total banyaknya mata kuliah dan banyaknya semester.
• $n$ baris berikutnya masing-masing berisi tiga bilangan bulat $s_i, g_i, t_i$ ($1 \le s_i, g_i \le 10^5, 1 \le t_i \le m$), dipisahkan oleh spasi, yang menyatakan satuan kredit, poin nilai, dan semester saat mata kuliah tersebut diambil. Dijamin bahwa $\forall 1 \le i \le 2m, t_i = \lfloor \frac{i+1}{2} \rfloor$.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $3 \times 10^5$, yaitu $\sum n \le 3 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan $n - 2m + 1$ baris, dengan setiap baris bersesuaian dengan $k = 2m, k = 2m+1, \dots, k = n$, yang menyatakan GPA maksimum yang dapat dicapai Xiao Bo jika ia hanya mengambil mata kuliah dari urutan ke-$1$ hingga ke-$k$ pada transkripnya.

Persyaratan Presisi Jawaban: Keluaran Anda akan dibandingkan dengan jawaban standar. Jika nilai keluaran peserta adalah $x$ dan jawaban standar adalah $y$, jawaban akan dinilai benar jika $\frac{|x-y|}{\max(1,|y|)} \le 10^{-6}$.

Contoh

Contoh 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