KOI Country consists of $N$ cities, each numbered $1, 2, \ldots, N$. City $1$ is the capital of KOI Country.

There are $N-1$ bidirectional roads in KOI Country. For every $i$ with $2 \le i \le N$, city $i$ is connected by a bidirectional road to city $P$, where $P < i$. The daily traffic volume of the road connecting city $i$ and city $P$ is $W$.

If a city $u$ lies on the simple path from city $1$ (the capital) to city $v$, then we define that city $u$ controls city $v$. The administrative region of city $i$ is defined as the set of all cities that city $i$ controls. Accordingly, the administrative region of city $1$ is all cities, and for every $i$ with $1 \le i \le N$, city $i$ belongs to its own administrative region.

If we view the road network of KOI Country as a tree rooted at city $1$, the administrative region of city $i$ coincides with the subtree rooted at city $i$.

A festival is planned to be held in each city of KOI Country. Normally, all roads are free to use, but when a festival is held, tolls may be collected on some roads to cover the cost of the festival.

When a festival is held in city $i$, some roads can be selected to collect tolls. The daily toll revenue is the sum of the daily traffic volumes of the roads on which tolls are collected. However, to reduce public dissatisfaction, the selected roads must satisfy the following two conditions:

1. On the simple path between any two cities in KOI Country, there are at most $K$ roads on which tolls are collected.
2. Both endpoints of every road on which tolls are collected must belong to the administrative region of city $i$.

For every $i$ with $1 \le i \le N$, assuming that a festival is held in city $i$, compute the maximum possible daily toll revenue.

Constraints

All given values are integers.

• $1 \le K < N \le 300\,000$
• For every $i$ with $2 \le i \le N$, $1 \le P < i$
• For every $i$ with $2 \le i \le N$, $0 \le W \le 10^9$

Scoring

Subtask 1 (4 points)

• $N \le 3\,000$

Subtask 2 (5 points)

• There is at most one city that is connected to three or more roads.

Subtask 3 (11 points)

• For the simple path $T$ connecting city $1$ and city $N$, from every city it takes at most $10$ roads to reach a city on $T$.

Subtask 4 (13 points)

• $N \le 100\,000$
• For every $i$ with $2 \le i \le N$, $W = 1$

Subtask 5 (8 points)

• For every $i$ with $2 \le i \le N$, $W = 1$

Subtask 6 (17 points)

• $N \le 100\,000$
• For every $i$ with $2 \le i \le N$, $W$ equals the number of cities in the administrative region of city $i$.

Subtask 7 (10 points)

• For every $i$ with $2 \le i \le N$, $W$ equals the number of cities in the administrative region of city $i$.

Subtask 8 (15 points)

• $N \le 100\,000$

Subtask 9 (17 points)

• No additional constraints.

Input Format

The first line contains two integers $N$ and $K$, separated by a space.

The next $N-1$ lines follow. The $(i-1)$-th of these lines ($2 \le i \le N$) contains two integers $P$ and $W$, separated by a space.

Output Format

Output $N$ lines in total. The $i$-th line ($1 \le i \le N$) should contain the maximum possible daily toll revenue when a festival is held in city $i$.

Example

Example 1

Input

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

Output

10
4
4
0
0
0
0

Example 2

Input

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

Output

14
4
4
0
0
0
0

Example 3

Input

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

Output

17
6
6
0
0
0
0

Example 4

Input

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

Output

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