Nel tempo libero Farmer John ha creato MooTube, servizio di condivisione video. Le mucche possono registrare, condividere e scoprire video divertenti. Ne hanno pubblicati $N$ ($1\le N\le100{,}000$), numerati $1\ldots N$, ma FJ non sa come aiutarle a trovare nuovi video di loro gusto.

Vuole per ogni video una lista di “video suggeriti”, raccomandando quelli più pertinenti ai video già guardati.

FJ definisce la “pertinenza” tra due video. Sceglie $N-1$ coppie e la calcola manualmente per ognuna. I video sono nodi di una rete, le coppie scelte vengono collegate, così che fra due video qualsiasi esista esattamente un cammino. La pertinenza della coppia è la minima pertinenza dei collegamenti su quel cammino.

FJ sceglie $K$ per suggerire accanto a ogni video tutti gli altri con pertinenza almeno $K$. Ma troppi potrebbero distrarre le mucche dalla produzione di latte! Vuole scegliere $K$ con attenzione e chiede risposte sulle raccomandazioni per certi $K$.

Input

La prima riga contiene $N,Q$ ($1\le Q\le100{,}000$).

Le successive $N-1$ righe descrivono coppie confrontate manualmente. Gli interi $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$) indicano collegamento tra $p_i,q_i$ di pertinenza $r_i$.

Le successive $Q$ righe sono domande. Gli interi $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$) chiedono, nella domanda $i$, quanti video saranno suggeriti a chi guarda $v_i$ se $K=k_i$.

Output

Stampa $Q$ righe; la riga $i$ risponde alla domanda $i$.

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

Spiegazione

Le pertinenze di $1,2$, di $2,3$ e di $2,4$ sono $3,2,4$. Quindi quelle di $1,3$, di $1,4$ e di $3,4$ sono $\min(3,2)=2$, $\min(3,4)=3$, $\min(2,4)=2$.

FJ domanda del video $2$ con $K=1$, di $1$ con $K=3$ e di $1$ con $K=4$. Con $K=1$, $2$ suggerisce $1,3,4$; con $K=4$, $1$ non suggerisce nulla; con $K=3$, $1$ suggerisce $2,4$.

Autore del problema: Jay Leeds