← 返回题目列表

AtCoder · arc201_f

F. CatCoder 三重竞赛

中文机器翻译题面 查看原题

分数: 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第二位作家