Nel tempo libero Farmer John ha creato un servizio di condivisione video chiamato MooTube. Le sue mucche possono registrarvi, condividere e scoprire molti video divertenti. Hanno già pubblicato $N$ video ($1 \leq N \leq 5000$), numerati $1 \ldots N$. Tuttavia FJ non sa come aiutarle a trovare nuovi video che potrebbero piacere loro.

FJ vuole creare un elenco di «video suggeriti» per ogni video MooTube, consigliando alle mucche i video più pertinenti rispetto a quelli che già guardano.

FJ definisce una misura di «pertinenza» che indica, come suggerisce il nome, quanto due video siano collegati. Sceglie $N-1$ coppie e ne calcola manualmente la pertinenza. Rappresenta poi i video come una rete: ogni video è un nodo e le $N-1$ coppie esaminate sono collegate. Ha scelto queste $N-1$ coppie in modo che tra due video qualsiasi esista esattamente un percorso di collegamenti. Definisce la pertinenza di qualsiasi coppia come la pertinenza minima di un collegamento lungo quel percorso.

Farmer John vuole scegliere $K$ affinché accanto a ogni video MooTube siano suggeriti tutti gli altri video con pertinenza rispetto ad esso almeno $K$. Teme però che troppi suggerimenti distraggano le mucche dalla produzione di latte! Vuole quindi scegliere con attenzione un $K$ adeguato. Aiutalo a rispondere a domande sui suggerimenti per particolari valori di $K$.

Input

La prima riga contiene $N$ e $Q$ ($1 \leq Q \leq 5000$).

Le successive $N-1$ righe descrivono le coppie confrontate manualmente. Ognuna contiene tre interi $p_i$, $q_i$ e $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$): i video $p_i$ e $q_i$ sono collegati con pertinenza $r_i$.

Le successive $Q$ righe descrivono le $Q$ domande di Farmer John. Ognuna contiene due interi $k_i$ e $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$): la domanda $i$ chiede quanti video saranno suggeriti agli spettatori del video $v_i$ se $K = k_i$.

Output

Stampa $Q$ righe. Nella riga $i$ stampa la risposta alla domanda $i$ di FJ.

Esempi

Input 1

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

Output 1

3
0
2

Nota

La pertinenza tra i video1 e2 è3, tra2 e3 è2 e tra2 e4 è4. Quindi quella tra1 e3 è $min(3, 2) = 2$, tra1 e4 è $min(3, 4) = 3$ e tra3 e4 è $min(2, 4) = 2$.

Farmer John vuole conoscere il numero di suggerimenti dal video2 con $K=1$, dal video1 con $K=3$ e dal video1 con $K=4$. Con $K=1$, al video2 sono suggeriti i video1,3 e4. Con $K=4$ non si suggerisce alcun video dal video1. Con $K=3$ si suggeriscono i video2 e4 dal video1.

Autore del problema: Jay Leeds