← 返回题目列表

Codeforces · 1861/F

F. 四色

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

Berland 扑克游戏的玩法如下。有 $$$n+1$$$ 人:$$$n$$$ 玩家,编号从 $$$1$$$ 到 $$$n$$$,以及庄家。庄家有一副牌,包含四种不同花色的牌(每种花色的牌张数不一定相同);这副牌中的牌数可以被 $$$n$$$ 整除。庄家将所有牌发给玩家,以便每个玩家收到相同数量的牌,并使用整副牌。

发牌后,每位玩家(独立)选择四种花色中的一种,并从手中丢弃所有不属于其所选花色的牌。游戏的获胜者是手中剩余牌张数最多的玩家。获胜者获得的分数为 $$$x - y$$$,其中 $$$x$$$ 是获胜者手中的牌数,$$$y$$$ 是所有其他玩家中最大的牌数;其他人都获得 $$$0$$$ 积分。请注意,这意味着如果有多个玩家拥有最大牌数,则每个人都会获得 $$$0$$$ 积分。

由于每个玩家都希望最大化获胜的几率,因此他们会选择手牌数量最多的花色。

Monocarp 是经销商。他已经给了玩家一些牌;第 $$$i$$$ 位玩家收到 $$$a_{i,j}$$$ 牌,花色为 $$$j$$$。请注意,此时玩家手中的牌张数不必相同。 Monocarp 的套牌中还剩下 $$$b_1, b_2, b_3, b_4$$$ 牌,花色分别为 $$$1, 2, 3, 4$$$。他必须将它们交给玩家,以便在发完所有牌后,每个玩家都拥有相同数量的牌。

对于每个玩家,根据游戏规则计算剩余牌的所有发牌方式中可以获得的最大点数。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — 玩家数量。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含四个整数 $$$a_{i,1}、a_{i,2}、a_{i,3}、a_{i,4}$$$ ($$$0 \le a_{i,j} \le 10^6$$$),其中 $$$a_{i,j}$$$ 是第 $$$j$$$ 花色的牌张数第 $$$i$$$ 位玩家当前拥有。

最后一行包含 $$$4$$$ 整数 $$$b_1, b_2, b_3, b_4$$$ ($$$0 \le b_j \le 10^6$$$),其中 $$$b_j$$$ 是 Monocarp 必须处理的第 $$$j$$$ 花色的牌张数。

对输入的附加限制:可以发完所有剩余的牌,以便每个玩家拥有相同数量的牌。

输出

打印 $$$n$$$ 整数。其中第 $$$i$$$ 应该是第 $$$i$$$ 玩家在处理剩余牌的所有可能方式中可以获得的最大点数。

示例

输入 #1

2
3 1 1 1
1 1 1 1
2 2 0 0

输出 #1

1 0

输入 #2

4
0 0 0 0
0 0 0 1
2 2 0 0
0 1 0 0
3 2 3 2

输出 #2

1 1 1 1

输入 #3

7
2 1 0 1
0 0 2 1
4 4 1 2
0 0 1 0
1 1 0 1
0 2 1 1
0 2 0 0
15 10 10 14

输出 #3

5 6 1 7 5 5 7