الوصف

شياو بو طالب جامعي مجتهد يهتم كثيرًا بأدائه الأكاديمي. في كل فصل دراسي، يكتسب ساعات معتمدة ونقاط تقدير مقابلة لعدة مقررات دراسية. تعد نقاط التقدير وسيلة لقياس الأداء في المقرر، بينما يعد المعدل التراكمي (GPA) مؤشرًا مهمًا للمستوى الأكاديمي العام للطالب. يأمل شياو بو في تحقيق أعلى معدل تراكمي ممكن.

تقدم الجامعة سياسة خاصة: في كل فصل دراسي، يمكن للطلاب اختيار تحويل درجة مقرر واحد على الأكثر إلى نظام «ناجح/راسب» (Pass/No Pass, PNP) (وبالطبع، يمكنهم أيضًا اختيار عدم تحويل أي مقرر إلى نظام PNP في فصول دراسية معينة). في نظام PNP، لا يتم تضمين نقاط التقدير لهذا المقرر في حساب المعدل التراكمي.

يعرف شياو بو أنه درس ما مجموعه $n$ من المقررات على مدار $m$ من الفصول الدراسية. وهو يعرف الساعات المعتمدة، ونقاط التقدير، والفصل الدراسي لكل مقرر في كشف درجاته، والتي يُرمز لها بـ $s_i, g_i, t_i$. من المضمون أن أول $2m$ من المقررات في كشف الدرجات تحقق ما يلي: الفصل الدراسي للمقرر رقم $i$ هو $\lfloor \frac{i+1}{2} \rfloor$ (وهذا يضمن دراسة مقررين على الأقل في كل فصل دراسي)، بينما لا يوجد ضمان مماثل للفصل الدراسي للمقررات المتبقية. يأمل شياو بو في اتخاذ قرارات مناسبة في كل فصل دراسي لتعظيم معدله التراكمي النهائي.

ومع ذلك، يعتقد شياو بو أن هذا سهل للغاية ويريد أن يعرف: لأي $k$ يحقق $2m \le k \le n$، إذا درس فقط المقررات من المقرر رقم $1$ إلى المقرر رقم $k$ في كشف درجاته، مع الأخذ في الاعتبار قرارات PNP لكل فصل دراسي، فما هو أقصى معدل تراكمي يمكنه تحقيقه؟

صيغة حساب المعدل التراكمي هي كما يلي: بافتراض وجود $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$)، مفصولة بمسافات، تمثل الساعات المعتمدة، ونقاط التقدير، والفصل الدراسي الذي دُرس فيه المقرر. من المضمون أن $\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$.

الإخراج

لكل حالة اختبار، اطبع $n - 2m + 1$ من الأسطر، حيث يقابل كل سطر $k = 2m, k = 2m+1, \dots, k = n$، ويمثل أقصى معدل تراكمي يمكن أن يحققه شياو بو إذا درس فقط المقررات من المقرر رقم $1$ إلى المقرر رقم $k$ في كشف درجاته.

متطلبات دقة الإجابة: ستتم مقارنة مخرجاتك مع الإجابة القياسية. إذا كانت قيمة مخرجات المتسابق هي $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