rainingseason

Raining Season

By the year 3018, Summer Informatics School had greatly grown. Hotel «Berendeetronik» had been chosen as a location of the school. The camp consists of \(n\) houses with \(n − 1\) pathways between them. It is possible to reach every house from each other using the pathways.

Everything was perfect until the rain started. The weather forecast promises that the rain will continue for \(m\) days. A special squad of teachers was able to measure that each pathway \(i\), connecting houses \(u_i\) and \(v_i\), could be passed in \(b_i\) seconds before the rain. Unfortunately, the rain erodes the roads, so with every day the time to pass the road will increase by \(a_i\) seconds. In other words, on the \(t^{th}\) (from zero) day after the start of the rain, it will take \(a_i \cdot t + b_i\) seconds to pass through this road.

Unfortunately, despite all the efforts of teachers, even in the year 3018 not all the students are in their houses by midnight. As by midnight all students have to go to bed, it is important to find the maximum travel time between all pairs of houses for each day, so every student knows the time when he has to run to his house.

Find the maximal travel times of the paths between any pair of houses after \(t = 0, t = 1, \ldots, t = m − 1\) days.

Input format

In the first line you are given two integers \(n\) and \(m\) — the number of houses in the camp and the number of raining days \((1 \leq n \leq 10^5; 1 \leq m \leq 10^6)\).

In the next \(n − 1\) lines you are given the integers \(u_i\), \(v_i\), \(a_i\), \(b_i\) — description of pathways \((1 \leq u_i, v_i \leq n; 0 \leq a_i \leq 10^5; 0 \leq b_i \leq 10^9)\). The \(i^{th}\) pathway connects houses \(u_i\) and \(v_i\), and in day \(t\) requires \(a_i \cdot t + b_i\) seconds to pass through.

It is guaranteed that every two houses are connected by a sequence of pathways.

Output format

Print \(m\) integers — the lengths of the longest path in the camp \(t = 0, t = 1, \ldots, t = m − 1\) days after the start of the rain.

Limits

Samples

In the first three days \((0 \leq t \leq 2)\) the longest path is between \(2^{nd}\) and \(3^{rd}\) houses, and its length is equal to \(100 + 100 = 200\) seconds.

In the third day \((t = 2)\) the road between houses \(1\) and \(4\) has length \(100\) and keeps increasing. So, in days \(t = 2, 3, 4, 5\) the longest path is between houses \(4\) and (\(1\) or \(2\)), and has length \(180 + 10t\). Notice, that in the day \(t = 2\) there are three pathways with length \(100\), so there are three maximal paths of equal length.

In the sixth day \((t = 5)\) pathway between first and fifth houses has length \(100\). So in every day with \(t = 5\) and further the longest path is between houses \(4\) and \(5\) and has length \(80 + 30t\).