KOI 国には $N$ 個の都市があり、それぞれ $1, 2, \ldots, N$ の番号が付けられている。都市 $1$ は KOI 国の首都である。
KOI 国には $N-1$ 本の双方向道路がある。すべての $2 \le i \le N$ について、都市 $i$ は都市 $P$（$P < i$）と 1 本の双方向道路で結ばれている。都市 $i$ と都市 $P$ を結ぶ道路の 1 日あたりの交通量は $W$ である。
都市 $u$ が都市 $1$（首都）から都市 $v$ への単純パス上に存在するとき、都市 $u$ は都市 $v$ を管轄すると定義する。都市 $i$ の行政区域とは、都市 $i$ が管轄するすべての都市の集合である。したがって、都市 $1$ の行政区域はすべての都市であり、また $1 \le i \le N$ のすべての $i$ について、都市 $i$ は自分自身の行政区域に属する。
KOI 国の道路網を都市 $1$ を根とする木として見ると、都市 $i$ の行政区域は都市 $i$ を根とする部分木に一致する。
KOI 国の各都市で祭りが開催される予定である。通常、すべての道路は無料で利用できるが、祭りが開催されると、その費用を賄うために一部の道路で通行料が徴収される場合がある。
都市 $i$ で祭りが開催されるとき、いくつかの道路を選んで通行料を徴収することができる。1 日あたりの通行料収入は、通行料を徴収する道路の 1 日あたりの交通量の総和である。ただし、市民の不満を減らすために、選ばれた道路は次の 2 つの条件を満たさなければならない。
- KOI 国内の任意の 2 都市間の単純パス上において、通行料を徴収する道路は高々 $K$ 本である。
- 通行料を徴収するすべての道路について、その両端点は都市 $i$ の行政区域に属していなければならない。
すべての $1 \le i \le N$ について、都市 $i$ で祭りが開催されると仮定したときに得られる、1 日あたりの通行料収入の最大値を求めよ。
制約
すべての入力値は整数である。
- $1 \le K < N \le 300\,000$
- すべての $2 \le i \le N$ について、$1 \le P < i$
- すべての $2 \le i \le N$ について、$0 \le W \le 10^9$
小課題
小課題 1（4 点）
- $N \le 3\,000$
小課題 2（5 点）
- 3 本以上の道路に接続されている都市が高々 1 つである。
小課題 3（11 点）
- 都市 $1$ と都市 $N$ を結ぶ単純パス $T$ に対し、任意の都市から $T$ 上の都市へ到達するのに必要な道路の本数が高々 $10$ である。
小課題 4（13 点）
- $N \le 100\,000$
- すべての $2 \le i \le N$ について、$W = 1$
小課題 5（8 点）
- すべての $2 \le i \le N$ について、$W = 1$
小課題 6（17 点）
- $N \le 100\,000$
- すべての $2 \le i \le N$ について、$W$ は都市 $i$ の行政区域に含まれる都市の数に等しい。
小課題 7（10 点）
- すべての $2 \le i \le N$ について、$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 日あたりの通行料収入の最大値を出力せよ。
例
例 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