F. Четыре масти
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Игра в берландский покер проводится следующим образом. Участвуют $$$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 \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$$$ — это количество карт $$$j$$$-й масти, которые Монокарп еще должен раздать.

Дополнительное ограничение на входные данные: оставшиеся карты можно раздать таким образом, чтобы у каждого игрока стало одинаковое количество карт.

Выходные данные

Выведите $$$n$$$ целых чисел, $$$i$$$-е из них — максимальное количество очков, которое может получить $$$i$$$-й игрок среди всех возможных способов раздачи оставшихся карт.

Примеры
Входные данные
2
3 1 1 1
1 1 1 1
2 2 0 0
Выходные данные
1 0
Входные данные
4
0 0 0 0
0 0 0 1
2 2 0 0
0 1 0 0
3 2 3 2
Выходные данные
1 1 1 1
Входные данные
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
Выходные данные
5 6 1 7 5 5 7