En su tiempo libre, Farmer John creó un servicio para compartir vídeos llamado MooTube. Sus vacas pueden grabar, compartir y descubrir muchos vídeos divertidos. Ya publicaron $N$ vídeos ($1 \leq N \leq 5000$), numerados $1 \ldots N$. Sin embargo, FJ no sabe cómo ayudarles a encontrar nuevos vídeos que les gusten.

FJ quiere crear una lista de «vídeos sugeridos» para cada vídeo de MooTube, recomendando así los vídeos más relacionados con los que las vacas ya ven.

FJ define una medida de «relevancia» que indica, como su nombre sugiere, cuánto se relacionan dos vídeos. Elige $N-1$ pares y calcula manualmente su relevancia. Después representa los vídeos como una red: cada vídeo es un nodo y los $N-1$ pares estudiados están conectados. Eligió los $N-1$ pares de modo que existe exactamente un camino entre dos vídeos cualesquiera. Define la relevancia de cualquier par como la mínima relevancia de una conexión en ese camino.

Farmer John quiere elegir $K$ para que junto a cada vídeo MooTube se sugieran todos los demás vídeos cuya relevancia con él sea al menos $K$. Pero teme que demasiadas sugerencias distraigan a las vacas de producir leche. Por ello quiere fijar cuidadosamente un $K$ adecuado. Ayúdale a responder preguntas sobre las sugerencias para ciertos valores de $K$.

Entrada

La primera línea contiene $N$ y $Q$ ($1 \leq Q \leq 5000$).

Las siguientes $N-1$ líneas describen los pares comparados manualmente. Cada una contiene tres enteros $p_i$, $q_i$ y $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$): los vídeos $p_i$ y $q_i$ están conectados con relevancia $r_i$.

Las siguientes $Q$ líneas describen las $Q$ preguntas de Farmer John. Cada una contiene dos enteros $k_i$ y $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$): la pregunta $i$ pide cuántos vídeos se sugerirán a quienes ven el vídeo $v_i$ si $K = k_i$.

Salida

Imprime $Q$ líneas. En la línea $i$ imprime la respuesta a la pregunta $i$ de FJ.

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

La relevancia de los vídeos1 y2 es3, la de2 y3 es2 y la de2 y4 es4. Por tanto, la de1 y3 es $min(3, 2) = 2$, la de1 y4 es $min(3, 4) = 3$ y la de3 y4 es $min(2, 4) = 2$.

Farmer John quiere saber cuántos vídeos se sugerirán desde el vídeo2 si $K=1$, desde el vídeo1 si $K=3$ y desde el vídeo1 si $K=4$. Con $K=1$, al vídeo2 se le sugieren los vídeos1,3 y4. Con $K=4$ no se sugiere ninguno desde el vídeo1. Con $K=3$ se sugieren los vídeos2 y4 desde el vídeo1.

Autor del problema: Jay Leeds