В спортивном соревновании приняло участие $$$N$$$ команд. Результат каждого участника каждой команды оценивается в некоторую сумму призовых денег. Однако по правилам соревнования команде выдаётся только один приз. В качестве суммы приза команды организаторы хотели выбрать медиану призовых денег её участников, но призовой бюджет уже зафиксирован. Жюри хочет избежать обвинений в предвзятости, поэтому было решено распределить призы так, чтобы сумма абсолютных разностей по всем участникам между заработанными и полученными деньгами была минимальной.
Распределите призы между командами.
В первой строке задано $$$1\le N \le 1000$$$ — число команд. В следующих $$$N$$$ строках записаны команды. Первое число в строке $$$1\le M_i \le 100$$$ — размер команды. Оставшиеся $$$M_i$$$ целых чисел $$$0 \le D_{ij} \le 10^6$$$ — призовые деньги заработанные участниками команды. В последней строке записано единственное целое число $$$1\le T \le 10^9$$$ — размер призового фонда.
Выведите в одной строке $$$N$$$ целых чисел $$$0 \le T_i \le 10^9$$$ — призы полученные командами. Весь призовой бюджет должен быть полностью израсходован, то есть $$$\sum_{i=1}^{N}T_i = T$$$. Также должна быть минимизирована величина $$$\sum_{i=1}^{N}\sum_{j=1}^{M_i}|D_{ij} - T_i|$$$. Если есть несколько оптимальных распределений призов, выведите любое из них.
2 3 5 4 1 3 1 2 3 6
4 2
2 2 1 1 2 1 1 4
3 1
2 1 0 2 0 1 3
2 1
4 1 1 1 1 1 1 1 1 1
0 0 0 1
В первом тесте организаторы могут выдать каждой команде её медиану. В остальных тестах им приходится изменять выдаваемые призы.
