Farmer John은 여가에 영상 공유 서비스 MooTube를 만들었다. 소는 재미있는 영상을 녹화하고 공유하고 발견할 수 있다. 이미 $N$개 ($1\le N\le100{,}000$)를 게시했고 번호는 $1\ldots N$이다. 하지만 FJ는 좋아할 만한 새 영상을 찾도록 어떻게 도울지 모른다.

각 영상에 “추천 영상” 목록을 만들어 이미 보는 영상과 가장 관련 있는 영상을 소에게 추천하려 한다.

FJ는 두 영상의 “관련성”을 정했다. $N-1$쌍을 골라 각각 손수 관련성을 계산한다. 영상을 정점, 선택한 쌍을 연결로 한 네트워크에서 임의의 두 영상 사이 경로가 정확히 하나가 되도록 선택했다. 두 영상의 관련성은 그 경로에 있는 연결들의 관련성 최솟값이다.

FJ는 $K$를 골라 각 영상 옆에 관련성이 $K$ 이상인 다른 모든 영상을 추천하려 한다. 하지만 너무 많으면 소가 우유 생산에 집중하지 못할 수도 있다! 따라서 신중히 $K$를 고르도록 특정 $K$들의 추천에 관한 질문에 답해 달라고 한다.

입력

첫 줄에 $N,Q$ ($1\le Q\le100{,}000$)가 주어진다.

다음 $N-1$줄은 손수 비교한 쌍이다. 정수 $p_i,q_i,r_i$ ($1\le p_i,q_i\le N;1\le r_i\le1{,}000{,}000{,}000$)는 $p_i,q_i$의 연결 관련성이 $r_i$임을 나타낸다.

다음 $Q$줄은 질문이다. 정수 $k_i,v_i$ ($1\le k_i\le1{,}000{,}000{,}000;1\le v_i\le N$)는 $K=k_i$일 때 $v_i$ 시청자에게 몇 영상을 추천하는지 묻는 $i$번째 질문이다.

출력

$Q$줄 출력하며 $i$번째 줄은 $i$번째 질문의 답이다.

예제

입력 1

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

출력 1

3
0
2

참고

$1,2$의 관련성은 $3$, $2,3$은 $2$, $2,4$는 $4$다. 따라서 $1,3$은 $\min(3,2)=2$, $1,4$는 $\min(3,4)=3$, $3,4$는 $\min(2,4)=2$다.

FJ는 $K=1$에서 영상 $2$, $K=3$에서 $1$, $K=4$에서 $1$의 추천 수를 묻는다. $K=1$에서 $2$는 $1,3,4$를 추천한다. $K=4$에서 $1$은 아무것도 추천하지 않지만 $K=3$에서는 $2,4$를 추천한다.

문제 출제: Jay Leeds