Farmer John は暇なときに動画共有サービス MooTube を作りました。牛は楽しい動画を撮影、共有、発見できます。既に $N$ 本（$1\le N\le100{,}000$）を投稿し、番号は $1\ldots N$ です。ただし FJ は好みそうな新動画の探し方をまだ思いつきません。

各 MooTube 動画に「おすすめ動画」一覧を作り、今見ている動画に最も関連する動画を牛に勧めたいと考えています。

FJ は 2 本の関連度を表す「関連性」を考え、$N-1$ 組を選んで各組を手動で計算します。動画を頂点、選んだ組を接続とするネットワークにします。任意の動画から別の動画へ接続をたどる経路がちょうど 1 本になるよう選びました。2 本の関連性はその経路上の接続の関連性の最小値とします。

FJ は $K$ を選び、各動画の横に関連性が $K$ 以上の他の動画をすべて勧めます。しかし多すぎると牛が気を取られて乳を作らなくなるかもしれません！慎重に適切な $K$ を選ぶため、いくつかの $K$ のおすすめに関する質問に答えてください。

入力

最初の行は $N,Q$（$1\le Q\le100{,}000$）です。

続く $N-1$ 行は手動比較した組です。各行の整数 $p_i,q_i,r_i$（$1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$）は動画 $p_i,q_i$ を関連性 $r_i$ の接続で結ぶことを表します。

続く $Q$ 行は質問です。各行の整数 $k_i,v_i$（$1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$）は、$K=k_i$ のとき動画 $v_i$ の視聴者に何本勧めるかという第 $i$ 問を表します。

出力

$Q$ 行を出力し、第 $i$ 行は第 $i$ 問の答えです。

入出力例

入力 1

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

出力 1

3
0
2

注記

$1,2$ の関連性は $3$、$2,3$ は $2$、$2,4$ は $4$ です。そのため $1,3$ は $\min(3,2)=2$、$1,4$ は $\min(3,4)=3$、$3,4$ は $\min(2,4)=2$ です。

FJ は $K=1$ の動画 $2$、$K=3$ の動画 $1$、$K=4$ の動画 $1$ のおすすめ数を知りたいです。$K=1$ では動画 $2$ に $1,3,4$、$K=4$ では動画 $1$ に何もなく、$K=3$ では動画 $1$ に $2,4$ を勧めます。

問題作成：Jay Leeds