En su tiempo libre, Farmer John creó MooTube para compartir videos. Sus vacas pueden grabar, compartir y descubrir videos divertidos. Ya publicaron $N$ ($1\le N\le100{,}000$), numerados $1\ldots N$, pero FJ no sabe cómo ayudarlas a encontrar nuevos videos que les gusten.

Quiere una lista de «videos sugeridos» para cada video, recomendando los más relacionados con los que ya miran.

FJ define la «relevancia» entre videos. Elige $N-1$ parejas y calcula la relevancia de cada una manualmente. Los videos son nodos de una red y conecta las parejas elegidas, de modo que entre dos videos cualesquiera hay exactamente un camino. Define la relevancia de una pareja como la mínima relevancia de las conexiones de ese camino.

FJ elige $K$ para sugerir junto a cada video todos los demás con relevancia al menos $K$. ¡Pero demasiados podrían distraer a las vacas de producir leche! Quiere elegirlo cuidadosamente y pide respuestas a preguntas sobre las sugerencias para ciertos $K$.

Entrada

La primera línea contiene $N,Q$ ($1\le Q\le100{,}000$).

Las siguientes $N-1$ líneas describen parejas comparadas manualmente. Los enteros $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$) indican una conexión entre $p_i,q_i$ con relevancia $r_i$.

Las siguientes $Q$ líneas describen preguntas. Los enteros $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$) preguntan, en la pregunta $i$, cuántos videos se sugerirán a quien mira $v_i$ si $K=k_i$.

Salida

Imprime $Q$ líneas; la línea $i$ responde a la pregunta $i$.

Ejemplos

Entrada 1

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

Salida 1

3
0
2

Nota

Las relevancias de $1,2$, de $2,3$ y de $2,4$ son $3,2,4$. Así las de $1,3$, de $1,4$ y de $3,4$ son $\min(3,2)=2$, $\min(3,4)=3$, $\min(2,4)=2$.

FJ pregunta por el video $2$ con $K=1$, por $1$ con $K=3$ y por $1$ con $K=4$. Con $K=1$, $2$ sugiere $1,3,4$; con $K=4$, $1$ no sugiere ninguno; con $K=3$, $1$ sugiere $2,4$.

Autor del problema: Jay Leeds