在经历了两年线上举办后，国际信息学奥林匹克（IOI）终于要线下举行了。ISC 和 ITC 像往常一样忙碌，参赛者们兴奋不已，家长们既自豪又紧张，但对线下举办最兴奋的人莫过于 Malnar 先生。他将再次品尝萨格勒布机场清晨的葡萄汁，再次品尝最美味的亚洲美食，再次享受每日的远足旅行。

你们中更有经验的人可能会问：“什么远足？！Malnar 先生几乎从不和代表团其他人一起参加组织好的远足。” 没错，他确实不参加，他会在活动前几个月就计划好自己的远足。

首先，他解决了所有租车物流问题，然后列出了他想访问的 $N$ 个城市的简短清单。他在地图上圈出这些城市，并将每对直接通过高速公路连接的城市连接起来。有趣的是，今年他恰好画了 $N - 1$ 条连接线，并意识到使用这些高速公路，每对城市之间都存在一条路径。

这还不是全部，在亚洲似乎可以购买 $M$ 种不同类型的高速贴纸（vignettes）。对于每条高速公路，已知需要拥有哪些高速贴纸子集。Malnar 先生立即用 $1$ 到 $M$ 的整数对所有不同类型的高速贴纸进行了编号。有趣的是，他成功地对它们进行了编号，使得为了通过第 $i$ 条高速公路，你需要购买所有编号大于或等于 $l_i$ 且小于或等于 $r_i$ 的高速贴纸。

类似地，他用 $1$ 到 $N$ 的整数对所有城市进行了编号，其中举办奥林匹克竞赛的印度尼西亚城市日惹（Yogyakarta）被标记为 $1$。

为了更好地规划路线，他决定请你编写一个程序，计算对于每个城市，从日惹旅行到该城市所需购买的最少高速贴纸数量。

输入格式

第一行包含任务描述中的整数 $N$ 和 $M$。

接下来的 $N - 1$ 行中，第 $i$ 行包含 $a_i, b_i, l_i$ 和 $r_i$，表示第 $i$ 条高速公路连接编号为 $a_i$ 和 $b_i$ 的城市（$1 \le a_i, b_i \le N, a_i \ne b_i$），并且通过该高速公路旅行需要购买区间 $[l_i, r_i]$ 内的高速贴纸（$1 \le l_i \le r_i \le M$）。

这些高速公路使得这 $N$ 个城市两两连通。

输出格式

输出共 $N - 1$ 行。第 $i$ 行应包含 Malnar 先生为了从日惹（编号为 $1$ 的城市）旅行到编号为 $i + 1$ 的城市所需购买的最少高速贴纸数量。

数据范围

样例

输入格式 1

6 6
1 2 2 4
1 3 1 4
2 4 3 5
2 5 5 6
3 6 2 3

输出格式 1

3
4
4
5
4

说明

• 为了旅行到编号为 2 的城市，你可以购买编号为 $(2, 3, 4)$ 的高速贴纸。
• 为了旅行到编号为 3 的城市，你可以购买编号为 $(1, 2, 3, 4)$ 的高速贴纸。
• 为了旅行到编号为 4 的城市，你可以购买编号为 $(2, 3, 4, 5)$ 的高速贴纸。
• 为了旅行到编号为 5 的城市，你可以购买编号为 $(2, 3, 4, 5, 6)$ 的高速贴纸。
• 为了旅行到编号为 6 的城市，你可以购买编号为 $(1, 2, 3, 4)$ 的高速贴纸。

输入格式 2

5 6
1 2 2 2
2 3 3 3
3 5 1 5
3 4 1 1

输出格式 2

1
2
3
5

说明

• 为了旅行到编号为 2 的城市，你可以购买编号为 $2$ 的高速贴纸。
• 为了旅行到编号为 3 的城市，你可以购买编号为 $(2, 3)$ 的高速贴纸。
• 为了旅行到编号为 4 的城市，你可以购买编号为 $(1, 2, 3)$ 的高速贴纸。
• 为了旅行到编号为 5 的城市，你可以购买编号为 $(1, 2, 3, 4, 5)$ 的高速贴纸。