Дерево

Задано зважене дерево. Знайдіть найкоротшу відстань між заданими вершинами.

Вхідні дані

Перший рядок містить кількість вершин у дереві $n(1\le n\le 150000)$. Вершини пронумеровано цілими числами від $0$ до $n-1$. У наступних $n-1$ рядках міститься по три цілих числа $u,v,w$, які відповідають ребру вагою $w(0\le w\le 1000)$, що з'єднує вершини $u$ та $v$. У наступному рядку міститься ціле число $m(1\le m\le 75000)$ — кількість запитів. У наступних $m$ рядках міститься по два числа — номери вершин, відстань між якими необхідно обчислити.

Вихідні дані

Для кожного запиту виведіть в окремому рядку одне число — шукану відстань.

Приклади