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

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

• 1 i c: изменить стоимость ребра с номером $i$ на $c$.
• 2 u v: вывести максимальную стоимость среди рёбер на простом пути из $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$.

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

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

Примеры

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

3
1 2 1
2 3 2
3
2 1 2
1 1 3
2 1 2

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

1
3