Имеется дерево (связный граф без циклов, неориентированный) из $N$ вершин. Вершины пронумерованы от $1$ до $N$, рёбра пронумерованы от $1$ до $N-1$.

Напишите программу, которая выполняет два следующих запроса:

• 1 u v: вывести стоимость пути из $u$ в $v$.
• 2 u v k: вывести $k$-ю вершину на пути из $u$ в $v$. $k$ не превосходит количества вершин, входящих в путь из $u$ в $v$.

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

Первая строка содержит целое число $N$ ($2 \le N \le 100\,000$).

Следующие $N-1$ строк содержат номера двух вершин $u$ и $v$, которые соединяет $i$-е ребро, и стоимость ребра $w$.

Следующая строка содержит количество запросов $M$ ($1 \le M \le 100\,000$).

Следующие $M$ строк содержат по одному запросу в строке.

Стоимость ребра — всегда натуральное число, не превосходящее $1\,000\,000$.

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

Для каждого запроса выведите результат в отдельной строке в порядке обработки.

Примеры

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

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
2
1 4 6
2 4 6 4

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

5
3