KOI 国由 $N$ 个城市组成，编号为 $1, 2, \ldots, N$。城市 $1$ 是 KOI 国的首都。

KOI 国中有 $N-1$ 条双向道路。对每个满足 $2 \le i \le N$ 的 $i$，城市 $i$ 通过一条双向道路与城市 $P$ 相连，其中 $P < i$。连接城市 $i$ 与城市 $P$ 的道路的日交通量为 $W$。

如果城市 $u$ 位于从城市 $1$（首都）到城市 $v$ 的简单路径上，则称城市 $u$ 控制 城市 $v$。城市 $i$ 的 行政区域 定义为城市 $i$ 所控制的所有城市的集合。相应地，城市 $1$ 的行政区域是所有城市，并且对每个满足 $1 \le i \le N$ 的 $i$，城市 $i$ 属于自己的行政区域。

如果我们把 KOI 国的道路网络视为一棵以城市 $1$ 为根的树，则城市 $i$ 的行政区域与以城市 $i$ 为根的子树一致。

计划在 KOI 国的每个城市举办节日。通常情况下，所有道路都可以免费通行，但在举办节日时，可能会在一些道路上收取通行费以覆盖节日成本。

当在城市 $i$ 举办节日时，可以选择一些道路来收取通行费。每日通行费收入等于所选收费道路的日交通量之和。然而，为了减少公众不满，所选道路必须满足以下两个条件：

1. 在 KOI 国任意两个城市之间的简单路径上，收取通行费的道路条数最多为 $K$。
2. 每一条收取通行费的道路的两个端点都必须属于城市 $i$ 的行政区域。

对每个满足 $1 \le i \le N$ 的 $i$，假设在城市 $i$ 举办节日，计算可能获得的每日通行费收入的最大值。

限制

所有给定值均为整数。

• $1 \le K < N \le 300,000$
• 对每个满足 $2 \le i \le N$ 的 $i$，$1 \le P < i$
• 对每个满足 $2 \le i \le N$ 的 $i$，$0 \le W \le 10^9$

子任务

子任务 1（4 分）

• $N \le 3,000$

子任务 2（5 分）

• 至多只有一个城市连接了三条或更多道路。

子任务 3（11 分）

• 对连接城市 $1$ 与城市 $N$ 的简单路径 $T$，从任意城市出发，到达路径 $T$ 上某个城市所经过的道路数最多为 $10$。

子任务 4（13 分）

• $N \le 100,000$
• 对每个满足 $2 \le i \le N$ 的 $i$，$W = 1$

子任务 5（8 分）

• 对每个满足 $2 \le i \le N$ 的 $i$，$W = 1$

子任务 6（17 分）

• $N \le 100,000$
• 对每个满足 $2 \le i \le N$ 的 $i$，$W$ 等于城市 $i$ 的行政区域中的城市数量。

子任务 7（10 分）

• 对每个满足 $2 \le i \le N$ 的 $i$，$W$ 等于城市 $i$ 的行政区域中的城市数量。

子任务 8（15 分）

• $N \le 100,000$

子任务 9（17 分）

• 无额外限制。

输入格式

第一行包含两个整数 $N$ 和 $K$，用空格分隔。

接下来 $N-1$ 行。第 $(i-1)$ 行（$2 \le i \le N$）包含两个整数 $P$ 和 $W$，用空格分隔。

输出格式

共输出 $N$ 行。第 $i$ 行（$1 \le i \le N$）应输出在城市 $i$ 举办节日时，每日通行费收入可能达到的最大值。

样例数据

样例 1

输入

7 2
1 5
1 5
2 2
2 2
3 2
3 2

输出

10
4
4
0
0
0
0

样例 2

输入

7 3
1 5
1 5
2 2
2 2
3 2
3 2

输出

14
4
4
0
0
0
0

样例 3

输入

7 3
1 5
1 5
2 3
2 3
3 3
3 3

输出

17
6
6
0
0
0
0

样例 4

输入

20 4
1 1
1 2
2 4
3 0
4 7
6 2
4 10
2 9
4 2
2 5
8 1
6 1
11 5
5 9
1 1
16 6
7 10
6 3
8 7

输出

78
60
9
41
9
16
10
8
0
0
5
0
0
0
0
6
0
0
0
0