CF1019E.Raining season

By the year 3018, Summer Informatics School has greatly grown. Hotel «Berendeetronik» has 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 had been perfect until the rains started. The weather forecast promises that rains will continue for $m$ days. A special squad of teachers was able to measure that the $i$-th pathway, connecting houses $u_i$ and $v_i$, before the rain could be passed in $b_i$ seconds. 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 maximal time between all the pairs of houses for each day, so every student would know the time when he has to run to his house.

Find all the maximal times of paths between every pairs of houses after $t=0$, $t=1$, ..., $t=m-1$ days.

到3018年，暑期信息学学校已大幅扩张。酒店「贝伦迪特罗尼克」被选定为该校的举办地点。营地由 $n$ 座房屋组成，房屋之间共有 $n-1$ 条通道相连，且任意两座房屋之间均可通过这些通道相互到达。

一切本都十分完美，直到大雨开始降临。天气预报显示，降雨将持续 $m$ 天。一支由教师组成的特别小队成功测得：第 $i$ 条通道（连接房屋 $u_i$ 和 $v_i$）在降雨前可通过时间为 $b_i$ 秒。不幸的是，雨水不断侵蚀道路，导致每过一天，通过该道路所需时间增加 $a_i$ 秒。换言之，在降雨开始后的第 $t$ 天（$t$ 从 $0$ 开始计数），通过该道路所需时间为 $a_i \cdot t + b_i$ 秒。

遗憾的是，尽管教师们竭尽全力，即使在3018年，也并非所有学生都能在午夜前回到自己的房屋。而根据规定，所有学生必须于午夜就寝，因此，每天计算出所有房屋对之间的最长路径时间至关重要，以便每位学生都能知晓自己最迟需何时奔向自己的房屋。

请计算在 $t = 0, 1, \dots, m-1$ 天（即降雨开始后第 $0$ 至第 $m-1$ 天）时，所有房屋对之间路径的最大耗时。

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 \le n \le 100\,000$; $1 \le m \le 1\,000\,000$).

In the next $n-1$ lines you are given the integers $u_i$, $v_i$, $a_i$, $b_i$ — description of pathways ($1 \le u_i, v_i \le n$; $0 \le a_i \le 10^5$; $0 \le b_i \le 10^9$). $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.

第一行给出两个整数 $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$ 秒。

保证任意两座房屋之间均存在由若干路径构成的连通序列。

Print $m$ integers — the lengths of the longest path in the camp after a $t=0, t=1, \ldots, t=m-1$ days after the start of the rain.

输出 $m$ 个整数——分别表示从开始下雨起经过 $t=0, t=1, \ldots, t=m-1$ 天后营地中最长路径的长度。

Let's consider the first example.

In the first three days ($0 \le t \le 2$) the longest path is between 2nd and 3rd 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 vertices 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 get 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$.

我们来考虑第一个例子。

在前三天（$0 \le t \le 2$）中，最长路径位于第 2 号与第 3 号房屋之间，其长度为 $100+100=200$ 秒。

在第三天（$t=2$），1 号与 4 号房屋之间的道路长度为 $100$，且持续增长。因此，在 $t=2,3,4,5$ 这几天中，最长路径位于顶点 4 与（顶点 1 或顶点 2）之间，其长度为 $180+10t$。注意，在第 $t=2$ 天，共有三条长度为 $100$ 的路径，因此存在三条等长的最长路径。

在第六天（$t=5$），1 号与 5 号房屋之间的路径长度达到 $100$。因此，从第 $t=5$ 天起，每一天的最长路径均位于 4 号与 5 号房屋之间，其长度为 $80+30t$。