分数: 1000 点
问题陈述
本题的问题设置与问题A部分共享。
今年 3333,CatCoder将举办CatCoder Triple Contest(简称C3C)。
有 N 有问题建议的作家。 每个作者的问题提案分为 5 按难度类型:地狱、困难、中等、简单、婴儿和 i第作者有 A_i,B_i,C_i,D_i,E_i 分别为地狱、困难、中等、简单、婴儿的问题建议。
每个C3C同时持有 3 部门,Div.1、Div.2 和 Div.3。各部门所需的问题建议如下:
- Div.1:来自同一作者的一个地狱、一个困难和一个中等问题提案
- Div.2:来自同一作者的一份困难问题、一份中等问题和一份简单问题提案
- Div.3:来自同一作者的 1 个 Medium、1 个 Easy 和 1 个 Baby 问题提案
请注意 Div.1、Div.2 和 Div.3 的作者不一定必须相同。 此外,每个问题提案最多可用于一个 C3C 的一个部门。
对于 k=1,2,\dots,N,让 X_k 是仅使用第一个问题提案可以举行 C3C 的最大次数 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- 第行应包含 X_1,X_2,\dots ,X_N 用空格分隔 i- 第一个测试用例。
示例输入 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
对于第一个测试用例,例如当 k=2,可举办C3C 2 次使用问题建议如下:
| 第 1 区 | 第 2 区 | 第 3 区 | |
|---|---|---|---|
| 1第一时间 | 地狱,困难,中等 1st 作家 | 困难、中等、容易 1st 作家 | 中等,简单,宝贝来自 2第二位作家 |
| 2第n次 | 地狱,困难,中等 2第二位作家 | 困难、中等、容易 1st 作家 | 中等,简单,宝贝来自 2第二位作家 |