Сипаттама

Сяо Бо — өзінің оқу үлгеріміне өте мұқият қарайтын еңбекқор университет студенті. Әр семестрде ол бірнеше пән бойынша кредиттер мен сәйкес баллдар (грейд-пойнттар) жинайды. Баллдар — пән бойынша үлгерімді өлшеу тәсілі, ал орташа балл (GPA) — студенттің жалпы академиялық деңгейінің маңызды көрсеткіші. Сяо Бо мүмкіндігінше ең жоғары GPA-ға қол жеткізгісі келеді.

Университет арнайы ереже ұсынады: әр семестрде студенттер ең көп дегенде бір пәннің бағасын «Өтті/Өтпеді» (Pass/No Pass, PNP) режиміне ауыстыруды таңдай алады (әрине, кейбір семестрлерде ешқандай пәнді PNP режиміне ауыстырмауды да таңдай алады). PNP режимінде бұл пәннің балы GPA есептеуіне қосылмайды.

Сяо Бо $m$ семестр ішінде барлығы $n$ пән оқығанын біледі. Ол транскриптіндегі әрбір пәннің кредитін, балын және семестрін біледі, олар $s_i, g_i, t_i$ деп белгіленеді. Транскрипттегі алғашқы $2m$ пән келесі шартты қанағаттандыратынына кепілдік беріледі: $i$-ші пәннің семестрі $\lfloor \frac{i+1}{2} \rfloor$ мәніне тең (бұл әр семестрде кемінде екі пән оқылатынын қамтамасыз етеді), ал қалған пәндердің семестріне мұндай кепілдік берілмейді. Сяо Бо қорытынды GPA мәнін барынша арттыру үшін әр семестрде орынды шешім қабылдағысы келеді.

Алайда Сяо Бо бұл тым оңай деп ойлайды және мынаны білгісі келеді: $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$ жол шығарыңыз; олардың әрқайсысы Сяо Бо транскриптіндегі тек $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 1

7.0000000000
6.5000000000
6.2631578947
6.3913043478
9.0000000000
9.3750000000
8.3000000000
8.1818181818
7.6470588235
7.2500000000