In seiner Freizeit hat Farmer John den Videodienst MooTube entwickelt. Kühe können lustige Videos aufnehmen, teilen und entdecken. Bereits $N$ Videos ($1\le N\le100{,}000$), nummeriert $1\ldots N$, wurden veröffentlicht. FJ weiß aber nicht, wie er ihnen beim Finden neuer passender Videos helfen soll.

Er möchte zu jedem MooTube-Video eine Liste „empfohlener Videos“, die am stärksten zu den bereits angesehenen passen.

FJ entwirft die „Relevanz“ zweier Videos. Er wählt $N-1$ Paare und berechnet sie jeweils von Hand. Er stellt die Videos als Knoten eines Netzes dar und verbindet die gewählten Paare so, dass zwischen beliebigen Videos genau ein Weg existiert. Die Relevanz eines Paars ist das Minimum der Relevanzen der Verbindungen auf diesem Weg.

FJ wählt $K$, um neben jedem Video alle anderen mit Relevanz mindestens $K$ zu empfehlen. Zu viele könnten die Kühe jedoch von der Milchproduktion ablenken! Er möchte $K$ sorgfältig wählen und bittet um Antworten auf Fragen über Empfehlungen für bestimmte $K$.

Eingabe

Die erste Zeile enthält $N,Q$ ($1\le Q\le100{,}000$).

Die nächsten $N-1$ Zeilen beschreiben von Hand verglichene Paare. Ganze Zahlen $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$) geben eine Verbindung von $p_i,q_i$ mit Relevanz $r_i$ an.

Die nächsten $Q$ Zeilen sind Fragen. Ganze Zahlen $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$) fragen in Frage $i$, wie viele Videos Zuschauern von $v_i$ bei $K=k_i$ empfohlen werden.

Ausgabe

Gib $Q$ Zeilen aus; Zeile $i$ beantwortet Frage $i$.

Beispiele

Eingabe 1

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

Ausgabe 1

3
0
2

Hinweis

Die Relevanzen von $1,2$, von $2,3$ und von $2,4$ sind $3,2,4$. Daher ergeben sich für $1,3$, für $1,4$ und für $3,4$ die Werte $\min(3,2)=2$, $\min(3,4)=3$, $\min(2,4)=2$.

FJ fragt nach Video $2$ bei $K=1$, nach $1$ bei $K=3$ und nach $1$ bei $K=4$. Bei $K=1$ empfiehlt $2$ die Videos $1,3,4$; bei $K=4$ empfiehlt $1$ keines; bei $K=3$ empfiehlt $1$ die Videos $2,4$.

Autor der Aufgabe: Jay Leeds