/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 1000 点
問題文
この問題の問題設定は A 問題と一部共通しています。
3333 年の CatCoder では、CatCoder Triple Contest（以下、C3C と略します）を開催することになりました。
いま、問題案を持っている writer が N 人います。 各 writer の問題案は難易度によって Hell, Hard, Medium, Easy, Baby の 5 種類に分類されており、i 人目の writer が持っている Hell, Hard, Medium, Easy, Baby の問題案の個数はそれぞれ A_i,B_i,C_i,D_i,E_i です。
各 C3C では Div.1, Div.2, Div.3 の 3 部門を同時に 1 つずつ開催します。それぞれの部門の開催に必要な問題案は以下の通りです。
- Div.1：同じ writer の Hell, Hard, Medium の問題案を 1 つずつ
- Div.2：同じ writer の Hard, Medium, Easy の問題案を 1 つずつ
- Div.3：同じ writer の Medium, Easy, Baby の問題案を 1 つずつ
ここで、Div.1, Div.2, Div.3 の writer は必ずしも同じである必要がない点に注意して下さい。 また、各問題案は高々 1 回の C3C の 1 つの部門にしか使用出来ません。
k=1,2,\dots,N について、1 人目から k 人目までの k 人の writer の問題案のみを使用することによって C3C を開催出来る回数の最大値を X_k とします。X_1,X_2,\dots ,X_N を求めて下さい。
T 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。
制約
- 1 \le T \le 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le A_i,B_i,C_i,D_i,E_i \le 10^9
- 全てのテストケースにおける N の総和は 2 \times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N A_1 B_1 C_1 D_1 E_1 A_2 B_2 C_2 D_2 E_2 \vdots A_N B_N C_N D_N E_N
出力
T 行出力せよ。
i 行目には i 番目のテストケースについて、X_1,X_2,\dots ,X_N を空白区切りで出力せよ。
入力例 1
3 2 3 3 3 3 3 3 1 4 2 5 7 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10 145852338 455046273 447701888 302317605 187706517 469056787 117990013 461926296 216907828 419205454 89931495 63942616 324197994 555154220 469433755 285221794 487750820 398191999 232324766 44467392 356205020 422423283 451558541 314957395 11846473 212753197 384933474 328150388 111956686 11132031 414426705 377305504 500797865 354689082 115544977 176361367 59266253 439600074 328676554 233005233 310994713 74852265 430187235 889232556 487055975 22464564 297489263 186185204 29275688 641606972
出力例 1
1 2 333333333 666666666 1000000000 1333333333 1666666666 2000000000 2333333333 145852338 259612716 314817258 501663240 646419826 751331137 911803212 1016363776 1143191852 1169061978
1 つ目のテストケースについて、例えば k=2 のときは以下のように問題案を使用することにより C3C を 2 回開催出来ます。
| Div.1 | Div.2 | Div.3 | |
|---|---|---|---|
| 第 1 回 | 1 人目の writer の Hell, Hard, Medium | 1 人目の writer の Hard, Medium, Easy | 2 人目の writer の Medium, Easy, Baby |
| 第 2 回 | 2 人目の writer の Hell, Hard, Medium | 1 人目の writer の Hard, Medium, Easy | 2 人目の writer の Medium, Easy, Baby |
Score : 1000 points
Problem Statement
The problem setting of this problem is partially shared with Problem A.
In the year 3333, CatCoder will hold the CatCoder Triple Contest (abbreviated as C3C).
There are N writers who have problem proposals. Each writer's problem proposals are classified into 5 types by difficulty: Hell, Hard, Medium, Easy, Baby, and the i-th writer has A_i,B_i,C_i,D_i,E_i problem proposals of Hell, Hard, Medium, Easy, Baby, respectively.
Each C3C simultaneously holds 3 divisions, Div.1, Div.2, and Div.3. The problem proposals required for each division are as follows:
- Div.1: One Hell, one Hard, and one Medium problem proposal from the same writer
- Div.2: One Hard, one Medium, and one Easy problem proposal from the same writer
- Div.3: One Medium, one Easy, and one Baby problem proposal from the same writer
Note that the writers for Div.1, Div.2, and Div.3 do not necessarily have to be the same. Also, each problem proposal can be used in at most one division of one C3C.
For k=1,2,\dots,N, let X_k be the maximum number of times C3C can be held using only the problem proposals of the first k writers. Find X_1,X_2,\dots ,X_N.
T test cases are given, so find the answer for each.
Constraints
- 1 \le T \le 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le A_i,B_i,C_i,D_i,E_i \le 10^9
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A_1 B_1 C_1 D_1 E_1 A_2 B_2 C_2 D_2 E_2 \vdots A_N B_N C_N D_N E_N
Output
Output T lines.
The i-th line should contain X_1,X_2,\dots ,X_N separated by spaces for the i-th test case.
Sample Input 1
3 2 3 3 3 3 3 3 1 4 2 5 7 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10 145852338 455046273 447701888 302317605 187706517 469056787 117990013 461926296 216907828 419205454 89931495 63942616 324197994 555154220 469433755 285221794 487750820 398191999 232324766 44467392 356205020 422423283 451558541 314957395 11846473 212753197 384933474 328150388 111956686 11132031 414426705 377305504 500797865 354689082 115544977 176361367 59266253 439600074 328676554 233005233 310994713 74852265 430187235 889232556 487055975 22464564 297489263 186185204 29275688 641606972
Sample Output 1
1 2 333333333 666666666 1000000000 1333333333 1666666666 2000000000 2333333333 145852338 259612716 314817258 501663240 646419826 751331137 911803212 1016363776 1143191852 1169061978
For the first test case, for example when k=2, C3C can be held 2 times by using problem proposals as follows:
| Div.1 | Div.2 | Div.3 | |
|---|---|---|---|
| 1st time | Hell, Hard, Medium from the 1st writer | Hard, Medium, Easy from the 1st writer | Medium, Easy, Baby from the 2nd writer |
| 2nd time | Hell, Hard, Medium from the 2nd writer | Hard, Medium, Easy from the 1st writer | Medium, Easy, Baby from the 2nd writer |