Alice と Bob の住む国には $N$ 個の駅があり、$2$ つの駅を結ぶ $M$ 本の路線があります。それぞれの駅には番号 $1, 2, \dots, N$ が、それぞれの路線には番号 $1, 2, \dots, M$ が付けられており、路線 $i$ は駅 $A_i$ と駅 $B_i$ の間を双方向に結び、$C_i$ の時間で移動することができます。ここで、どの駅も $1$ 本以上の路線を用いて互いに行き来することが可能であることが保証されます。

Alice は駅 $1$ の近くに、Bob は駅 $N$ の近くにそれぞれ住んでいます。ある日、$2$ 人は駅の近くで待ち合わせをすることにしました。

ただし、この国は通信技術が発達しておらず、逐一互いの居場所を連絡することができないため、 $2$ 人は時刻 $0$ に最寄駅を同時に出発し、路線のみを用いて駅間を移動して時刻 $K$ までにどこかの駅で会うことを予め決めました。

ここで、各駅での滞在時間や乗り換えにかかる時間、および路線の待ち時間は考慮しないものとします。

$2$ 人が時刻 $K$ までに会うことができる駅は何個あるか求めてください。$Q$ 個の整数 $K_1, K_2, \dots, K_Q$ が与えられるので、$K = K_1, K_2, \dots, K_Q$ についてそれぞれ答えてください。

Hard (125点)

• $2 \le N \le 10^5$
• $N - 1 \le M \le 2 \times 10^5$
• $1 \le A_i \lt B_i \le N$
• $i \ne j$ ならば $(A_i, B_i) \ne (A_j, B_j)$
• $1 \le C_i \le 10^5$
• どの駅も $1$ 本以上の路線を通って互いに行き来することが可能
• $1 \le Q \le 10^5$
• $0 \le K_i \le 10^9$
• 入力はすべて整数

Normal (50点)

• Hard の制約に以下の制約を追加
• $M = N - 1$
• $1 \le Q \le 100$

Easy (75点)

• Hard の制約に以下の制約を追加
• $3 \le N \le 100$
• $M = N - 1$
• $1 \le i \le M$ について $A_i = 2$ または $B_i = 2$
• $1 \le Q \le 100$

入力は以下の形式で標準入力から与えられます。

$Q$ 行出力してください。$i$ 行目には $K = K_i$ のときの答えを出力してください。