В свободное время Farmer John создал сервис обмена видео MooTube. Его коровы могут записывать, делиться и находить много забавных видео. Они уже опубликовали $N$ видео ($1 \leq N \leq 5000$), пронумерованных $1 \ldots N$. Однако FJ не знает, как помочь коровам найти новые видео, которые им понравятся.

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

FJ вводит показатель «связанности», определяющий, как следует из названия, насколько связаны два видео. Он выбирает $N-1$ пар и вручную вычисляет их связанность. Затем он представляет видео сетью: каждое видео — вершина, а $N-1$ рассмотренных пар соединены рёбрами. Эти $N-1$ пар выбраны так, что между любыми двумя видео существует ровно один путь соединений. Связанность любой пары определяется как минимальная связанность соединения на этом пути.

Farmer John хочет выбрать $K$, чтобы возле каждого видео MooTube рекомендовать все другие видео, связанность которых с ним не меньше $K$. Но он боится, что слишком много рекомендаций отвлекут коров от производства молока! Поэтому он хочет тщательно подобрать $K$. Помогите ответить на вопросы о рекомендациях при конкретных значениях $K$.

Входные данные

Первая строка содержит $N$ и $Q$ ($1 \leq Q \leq 5000$).

Следующие $N-1$ строк описывают пары видео, вручную сравненные FJ. Каждая содержит три целых числа $p_i$, $q_i$ и $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$): видео $p_i$ и $q_i$ соединены со связанностью $r_i$.

Следующие $Q$ строк описывают $Q$ вопросов Farmer John. Каждая содержит два целых числа $k_i$ и $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$): в вопросе $i$ спрашивается, сколько видео будет рекомендовано зрителю видео $v_i$ при $K = k_i$.

Выходные данные

Выведите $Q$ строк. В строке $i$ выведите ответ на вопрос $i$ FJ.

Примеры

Входные данные 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$.

Farmer John хочет узнать число рекомендаций для видео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