No tempo livre, Farmer John criou MooTube para compartilhar vídeos. Suas vacas podem gravar, compartilhar e descobrir vídeos divertidos. Já publicaram $N$ ($1\le N\le100{,}000$), numerados $1\ldots N$, mas FJ não sabe como ajudá-las a encontrar novos vídeos de que gostem.

Ele quer uma lista de “vídeos sugeridos” para cada vídeo, recomendando os mais relacionados aos que já assistem.

FJ define a “relevância” entre vídeos. Escolhe $N-1$ pares e calcula a relevância de cada um manualmente. Os vídeos são vértices de uma rede, os pares escolhidos são conectados, de modo que há exatamente um caminho entre quaisquer dois vídeos. A relevância de um par é a mínima relevância das conexões desse caminho.

FJ escolhe $K$ para sugerir, junto a cada vídeo, todos os outros com relevância pelo menos $K$. Mas muitos poderiam distrair as vacas da produção de leite! Ele quer escolher $K$ cuidadosamente e pede respostas a questões sobre sugestões para certos $K$.

Entrada

A primeira linha contém $N,Q$ ($1\le Q\le100{,}000$).

As próximas $N-1$ linhas descrevem pares comparados manualmente. Os inteiros $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$) indicam conexão entre $p_i,q_i$ de relevância $r_i$.

As próximas $Q$ linhas são questões. Os inteiros $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$) perguntam, na questão $i$, quantos vídeos serão sugeridos a quem vê $v_i$ se $K=k_i$.

Saída

Imprima $Q$ linhas; a linha $i$ responde à questão $i$.

Exemplos

Entrada 1

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

Saída 1

3
0
2

Explicação

As relevâncias de $1,2$, de $2,3$ e de $2,4$ são $3,2,4$. Logo as de $1,3$, de $1,4$ e de $3,4$ são $\min(3,2)=2$, $\min(3,4)=3$, $\min(2,4)=2$.

FJ pergunta sobre o vídeo $2$ com $K=1$, sobre $1$ com $K=3$ e sobre $1$ com $K=4$. Com $K=1$, $2$ sugere $1,3,4$; com $K=4$, $1$ não sugere nenhum; com $K=3$, $1$ sugere $2,4$.

Autor do problema: Jay Leeds