E. Сезон дождей
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

К 3018 году Летняя Компьютерная Школа довольно сильно увеличилась в размерах. Новым местом проведения был выбран отель «Берендеетроник». База состоит из $$$n$$$ домиков, между которыми есть $$$n-1$$$ тропинок, и между любыми домиками есть путь.

Все на базе было прекрасно, пока не начались дожди. Прогноз погоды обещает, что дожди будут идти $$$m$$$ дней. Специальный отряд преподавателей смог вычислить, что по $$$i$$$-й тропинке, соединяющей некие домики $$$u_i$$$ и $$$v_i$$$, до дождей можно пройти за $$$b_i$$$ секунд. Дождь же сильно размывает тропинку, и с каждым днем путь будет занимать на $$$a_i$$$ секунд больше, иными словами, в $$$t$$$-й (с нуля) день после начала дождя прохождение тропинки будет занимать $$$a_i \cdot t + b_i$$$ секунд.

К сожалению, несмотря на все прилагаемые усилия, даже в 3018 году не все школьники встречают вечерку и мягкий отбой в своих домиках. Поскольку к жесткому отбою все обязаны уснуть, необходимо вычислить максимальное время пути между всеми парами домиков для каждого дня, и вывесить его на доску объявлений, чтобы каждый школьник знал последний момент, когда он бежать к себе домой.

Посчитайте максимальное время пути между какой-либо парой домиков через $$$t=0$$$, $$$t=1$$$, ..., $$$t=m-1$$$ дней после начала дождей.

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

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — число домиков на базе и количество дождливых дней ($$$1 \le n \le 100\,000$$$; $$$1 \le m \le 1\,000\,000$$$).

В следующих $$$n-1$$$ строках даны четверки чисел $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, $$$b_i$$$ — описания тропинок ($$$1 \le u_i, v_i \le n$$$; $$$0 \le a_i \le 10^5$$$; $$$0 \le b_i \le 10^9$$$). $$$i$$$-я тропинка соединяет домики $$$u_i$$$ и $$$v_i$$$, и в день $$$t$$$ требует $$$a_i \cdot t + b_i$$$ секунд на прохождение.

Гарантируется, что между любыми двумя домиками есть путь.

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

Выведите $$$m$$$ чисел — значения самого длинного пути по базе через $$$t=0, t=1, \ldots, t=m-1$$$ дней после начала дождя.

Пример
Входные данные
5 10
1 2 0 100
1 3 0 100
1 4 10 80
1 5 20 0
Выходные данные
200 200 200 210 220 230 260 290 320 350
Примечание

Рассмотрим подробнее первый пример.

В первые три дня ($$$0 \le t \le 2$$$) самый длинный путь проходит между вторым и третьим домиками, и его длина равна $$$100+100=200$$$.

В третий день ($$$t=2$$$) дорожка между домиками 1 и 4 становится по длине равной $$$100$$$, и продолжает увеличиваться. Поэтому в дни с номерами $$$t=2, 3, 4, 5$$$ самый длинный путь проходит между вершинами 4 и 1 или 2, и имеет длину $$$180+10t$$$. Заметим, что в день $$$t=2$$$ есть три тропинки длиной 100, и есть три максимальных пути одинаковой длины.

В шестой день ($$$t=5$$$) тропинка между первым и пятым домиком по длине догоняет первые две, и становится равной 100. Таким образом, во все дни с $$$t=5$$$ и далее самый длинный путь проходит между вершинами 4 и 5, и имеет длину $$$80+30t$$$.