W wolnym czasie Farmer John stworzył serwis wideo MooTube. Krowy mogą nagrywać, udostępniać i odkrywać zabawne filmy. Zamieściły już $N$ ($1\le N\le100{,}000$), numerowanych $1\ldots N$, lecz FJ nie wie, jak pomóc im znaleźć nowe filmy, które polubią.

Chce listy „polecanych filmów” dla każdego filmu, zalecając najbardziej związane z już oglądanymi.

FJ definiuje „powiązanie” dwóch filmów. Wybiera $N-1$ par i ręcznie je oblicza. Filmy są wierzchołkami sieci, wybrane pary zostają połączone tak, że między dowolnymi filmami jest dokładnie jedna ścieżka. Powiązanie pary jest minimum powiązań połączeń na tej ścieżce.

FJ wybiera $K$, by obok każdego filmu polecać wszystkie inne o powiązaniu co najmniej $K$. Ale zbyt wiele mogłoby odciągnąć krowy od produkcji mleka! Chce starannie wybrać $K$ i prosi o odpowiedzi o poleceniach dla pewnych $K$.

Wejście

Pierwszy wiersz zawiera $N,Q$ ($1\le Q\le100{,}000$).

Następne $N-1$ wierszy opisuje ręcznie porównane pary. Całkowite $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$) oznaczają połączenie $p_i,q_i$ o powiązaniu $r_i$.

Następne $Q$ wierszy to pytania. Całkowite $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$) pytają w pytaniu $i$, ile filmów zostanie poleconych oglądającym $v_i$, gdy $K=k_i$.

Wyjście

Wypisz $Q$ wierszy; wiersz $i$ odpowiada na pytanie $i$.

Przykład

Wejście 1

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

Wyjście 1

3
0
2

Uwagi

Powiązania $1,2$, $2,3$, $2,4$ to $3,2,4$. Stąd dla $1,3$, $1,4$, $3,4$ wynoszą $\min(3,2)=2$, $\min(3,4)=3$, $\min(2,4)=2$.

FJ pyta o film $2$ przy $K=1$, o $1$ przy $K=3$ i o $1$ przy $K=4$. Przy $K=1$ film $2$ poleca $1,3,4$; przy $K=4$ film $1$ nie poleca nic; przy $K=3$ film $1$ poleca $2,4$.

Autor zadania: Jay Leeds