תיאור

Xiao Bo הוא סטודנט חרוץ הדואג מאוד להישגיו האקדמיים. בכל סמסטר, הוא צובר נקודות זכות ונקודות ציון מתאימות עבור מספר קורסים. נקודות ציון הן דרך למדוד ביצועים בקורס, בעוד שממוצע הציונים המשוקלל (GPA) הוא מדד חשוב לרמתו האקדמית הכוללת של הסטודנט. Xiao Bo מקווה להשיג את ה-GPA הגבוה ביותר האפשרי.

המוסד האקדמי מציע מדיניות מיוחדת: בכל סמסטר, סטודנטים יכולים לבחור להמיר את הציון של קורס אחד לכל היותר למצב "עובר/לא עובר" (Pass/No Pass, PNP) (כמובן, הם יכולים גם לבחור שלא להמיר אף קורס למצב PNP בסמסטרים מסוימים). במצב PNP, נקודות הציון של קורס זה לא ייכללו בחישוב ה-GPA.

Xiao Bo יודע שהוא למד בסך הכל $n$ קורסים על פני $m$ סמסטרים. הוא יודע מהן נקודות הזכות, נקודות הציון והסמסטר עבור כל קורס בגיליון הציונים שלו, המסומנים ב-$s_i, g_i, t_i$. מובטח כי $2m$ הקורסים הראשונים בגיליון הציונים מקיימים: הסמסטר של הקורס ה-$i$ הוא $\lfloor \frac{i+1}{2} \rfloor$ (דבר המבטיח שנלמדים לפחות שני קורסים בכל סמסטר), בעוד שהסמסטר עבור שאר הקורסים אינו מובטח מראש. Xiao Bo מקווה לקבל החלטות נבונות בכל סמסטר כדי למקסם את ה-GPA הסופי שלו.

עם זאת, Xiao Bo חושב שזה קצת קל מדי ורוצה לדעת: עבור כל $k$ המקיים $2m \le k \le n$, אם הוא לוקח רק את הקורסים מהקורס ה-$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$), מופרדים ברווחים, המייצגים את נקודות הזכות, נקודות הציון והסמסטר שבו נלמד הקורס. מובטח כי $\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$, ומייצגת את ה-GPA המקסימלי ש-Xiao Bo יכול להשיג אם הוא לוקח רק את הקורסים מהקורס ה-$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