В свободное время Farmer John создал сервис обмена видео MooTube. Коровы записывают, делятся и находят забавные видео. Уже опубликовано $N$ видео ($1\le N\le100{,}000$), пронумерованных $1\ldots N$. Но FJ не знает, как помочь находить новые видео по вкусу.

Он хочет для каждого видео MooTube список «рекомендованных видео», наиболее связанных с уже просматриваемыми.

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$) означают, что вопрос $i$ спрашивает число рекомендаций зрителям видео $v_i$ при $K=k_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 интересуют видео $2$ при $K=1$, видео $1$ при $K=3$ и видео $1$ при $K=4$. При $K=1$ видео $2$ рекомендует $1,3,4$; при $K=4$ у $1$ рекомендаций нет; при $K=3$ у $1$ рекомендуются $2,4$.

Автор задачи: Jay Leeds