310624: CF1861F. Four Suits

F. Four Suitstime limit per test6 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

The game of Berland poker is played as follows. There are $n+1$ people: $n$ players, numbered from $1$ to $n$, and the dealer. The dealer has a deck which contains cards of four different suits (the number of cards of each suit is not necessarily the same); the number of cards in the deck is divisible by $n$. The dealer gives all cards to the players, so that every player receives the same number of cards, and the whole deck is used.

After the cards are dealt, every player chooses one of four suits (independently) and discards all cards from their hand which do not belong to their chosen suit. The winner of the game is the player with the maximum number of cards left in their hand. The number of points the winner receives is $x - y$, where $x$ is the number of cards in the winner's hand, and $y$ is the maximum number of cards among all other players; everyone else receives $0$ points. Note that it means that if there are multiple players with the maximum number of cards, everyone receives $0$ points.

Since every player wants to maximize their odds to win, they will choose a suit with the maximum number of cards in their hand.

Monocarp is the dealer. He has already given some cards to the players; the $i$-th player received $a_{i,j}$ cards of suit $j$. Note that the number of cards in players' hands don't have to be the same at this moment. Monocarp has $b_1, b_2, b_3, b_4$ cards of suit $1, 2, 3, 4$ respectively left in his deck. He has to give them to the players so that, after all cards are dealt, every player has the same number of cards.

For each player, calculate the maximum number of points they can receive among all ways to deal the remaining cards according to the rules of the game.

Input

The first line of the input contains one integer $n$ ($2 \le n \le 5 \cdot 10^4$) — the number of players.

Then $n$ lines follow. The $i$-th of them contains four integers $a_{i,1}, a_{i,2}, a_{i,3}, a_{i,4}$ ($0 \le a_{i,j} \le 10^6$), where $a_{i,j}$ is the number of cards of the $j$-th suit that the $i$-th player currently has.

The last line contains $4$ integers $b_1, b_2, b_3, b_4$ ($0 \le b_j \le 10^6$), where $b_j$ is the number of cards of the $j$-th suit Monocarp has to deal yet.

Additional constraint on the input: it is possible to deal all of the remaining cards so that every player has the same number of cards.

Output

Print $n$ integers. The $i$-th of them should be the maximum number of points the $i$-th player can get among all possible ways to deal the remaining cards.

ExamplesInput

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

Output

1 0 

Input

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

Output

1 1 1 1 

Input

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

Output

5 6 1 7 5 5 7 

**题目大意：**
贝尔兰扑克游戏的规则是这样的。有n+1个人：n个玩家，编号从1到n，以及一个庄家。庄家有一副包含四种不同花色的牌（每种花色的牌数不一定相同）；牌的总数是n的倍数。庄家将所有牌分给玩家，使得每个玩家收到的牌数相同，且整副牌都被用上。

发牌后，每个玩家独立地选择四种花色中的一种，并丢弃手中不属于他们选择花色的所有牌。游戏中胜者是手中剩余牌数最多的玩家。胜者得分为x-y，其中x是胜者手中的牌数，y是所有其他玩家手中牌数的最大值；其他玩家得分为0。注意，如果有多个玩家手中的牌数最多，那么所有人都得0分。

因为每个玩家都想最大化自己获胜的概率，所以他们都会选择手中数量最多的花色。

莫诺卡普是庄家。他已经给玩家发了一些牌；第i个玩家收到了a_{i,j}张j花色的牌。注意，此时玩家手中的牌数可以不同。莫诺卡普手中还有b_1, b_2, b_3, b_4张1, 2, 3, 4花色的牌。他必须将这些牌发给玩家，以便在所有牌发完后，每个玩家都有相同数量的牌。

对于每个玩家，计算在所有发牌方式中他们能获得的最大分数。

**输入数据格式：**
第一行输入一个整数n（2≤n≤5×10^4）——玩家数量。

接下来n行，每行包含四个整数a_{i,1}, a_{i,2}, a_{i,3}, a_{i,4}（0≤a_{i,j}≤10^6），其中a_{i,j}是第i个玩家当前拥有的第j花色的牌数。

最后一行包含4个整数b_1, b_2, b_3, b_4（0≤b_j≤10^6），其中b_j是莫诺卡普还需要发的第j花色的牌数。

输入的附加条件：可以发完所有剩余的牌，使得每个玩家都有相同数量的牌。

**输出数据格式：**
输出n个整数。第i个数表示在第i个玩家所有可能的发牌方式中能获得的最大分数。**题目大意：** 贝尔兰扑克游戏的规则是这样的。有n+1个人：n个玩家，编号从1到n，以及一个庄家。庄家有一副包含四种不同花色的牌（每种花色的牌数不一定相同）；牌的总数是n的倍数。庄家将所有牌分给玩家，使得每个玩家收到的牌数相同，且整副牌都被用上。 发牌后，每个玩家独立地选择四种花色中的一种，并丢弃手中不属于他们选择花色的所有牌。游戏中胜者是手中剩余牌数最多的玩家。胜者得分为x-y，其中x是胜者手中的牌数，y是所有其他玩家手中牌数的最大值；其他玩家得分为0。注意，如果有多个玩家手中的牌数最多，那么所有人都得0分。 因为每个玩家都想最大化自己获胜的概率，所以他们都会选择手中数量最多的花色。 莫诺卡普是庄家。他已经给玩家发了一些牌；第i个玩家收到了a_{i,j}张j花色的牌。注意，此时玩家手中的牌数可以不同。莫诺卡普手中还有b_1, b_2, b_3, b_4张1, 2, 3, 4花色的牌。他必须将这些牌发给玩家，以便在所有牌发完后，每个玩家都有相同数量的牌。 对于每个玩家，计算在所有发牌方式中他们能获得的最大分数。 **输入数据格式：** 第一行输入一个整数n（2≤n≤5×10^4）——玩家数量。 接下来n行，每行包含四个整数a_{i,1}, a_{i,2}, a_{i,3}, a_{i,4}（0≤a_{i,j}≤10^6），其中a_{i,j}是第i个玩家当前拥有的第j花色的牌数。 最后一行包含4个整数b_1, b_2, b_3, b_4（0≤b_j≤10^6），其中b_j是莫诺卡普还需要发的第j花色的牌数。 输入的附加条件：可以发完所有剩余的牌，使得每个玩家都有相同数量的牌。 **输出数据格式：** 输出n个整数。第i个数表示在第i个玩家所有可能的发牌方式中能获得的最大分数。