К 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\) дней после начала дождей.
Выходные данные
Выведите \(m\) чисел — значения самого длинного пути по базе через \(t=0, t=1, \ldots, t=m-1\) дней после начала дождя.
Примечание
Рассмотрим подробнее первый пример.
В первые три дня (\(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|