Mirko は、$N$ 個の部屋が $N-1$ 本の廊下でつながった大きな家に住んでいます。各廊下は異なる二つの部屋をつなぎ、すべての部屋は互いに行き来できます。各廊下の長さは $1$ メートルです。Mirko は家の部屋をよく掃除しますが、廊下はめったに掃除しません。廊下にほこりがたまったので、今から掃除機をかけようとしています。

残念ながら、どの掃除機にも長さに限りのある電源コードがあります。各部屋にはコンセントがあり、掃除機を動かすにはいずれかの部屋のコンセントに接続しなければなりません。Mirko は部屋 $1$ から出発し、次の行動ができます。

掃除機が電源に接続されていない場合、次の行動ができます。

• 現在いる部屋で掃除機をコンセントに接続する。
• 掃除機を持って隣接する部屋の一つへ移動する。廊下を通るのに $1$ 分かかる。

掃除機が電源に接続されている場合、次の行動ができます。

• 掃除機を接続した部屋にいる場合、コンセントから外す。
• 隣接する廊下の一つを通り、その途中で廊下に掃除機をかける。これはコードが十分に長い場合に限って可能である。つまり、掃除機を接続した部屋から移動先の部屋までの距離が、コードの長さ以下でなければならない。廊下の掃除には $1$ 分かかる。

Mirko の掃除機が壊れてしまいました！今、彼は $Q$ 台の掃除機がある店にいます。$i$ 番目の掃除機のコードの長さは $r_i$ メートルです。それぞれの掃除機について、その掃除機を買った場合にすべての廊下の掃除が最短でどれくらいかかるかを知りたいと思っています。その時間を求めるのを手伝ってください！

入力

最初の行には、部屋の数と掃除機の数を表す自然数 $N$ と $Q$ が与えられます。

続く $N-1$ 行には自然数 $x_i$ と $y_i$（$1\le x_i,y_i\le N$, $x_i\ne y_i$）が与えられ、部屋 $x_i$ と部屋 $y_i$ の間に廊下があることを表します。

最後の行には、掃除機のコードの長さを表す $Q$ 個の数 $r_i$（$1\le r_i\le N$）が与えられます。

出力

唯一の行に $Q$ 個の数を出力してください。$i$ 番目の数は、$i$ 番目の掃除機を使った場合の最短の掃除時間を表します。

小課題

すべての小課題で $2\le N\le3\cdot10^5$ および $1\le Q\le3\cdot10^5$ が成り立ちます。

入出力例

入力 1

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

出力 1

8 4

入力 2

10 2
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10
1 3

出力 2

24 16

入力 3

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

出力 3

6 12

注記

最初の入出力例の説明：

コードの長さが $2$ メートルの掃除機で Mirko がすべての廊下を最短時間で掃除する方法の一つは、次のとおりです。

• 部屋 $1$ から部屋 $3$ まで歩く。（$2$ 分）
• 部屋 $3$ で掃除機をコンセントに接続する。
• 部屋 $3$ と $4$ の間、および部屋 $4$ と $5$ の間の廊下を掃除する。（$2$ 分）
• 部屋 $3$ に戻る。（$2$ 分）
• 部屋 $3$ と $2$ の間、および部屋 $2$ と $1$ の間の廊下を掃除する。（$2$ 分）これですべての廊下の掃除が完了する。