Dane jest drzewo (spójny graf nieskierowany bez cykli) składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a krawędzie od $1$ do $N-1$. Napisz program wykonujący następujące dwa rodzaje zapytań:

• 1 i c: zmień koszt $i$-tej krawędzi na $c$.
• 2 u v: wypisz największy koszt wśród krawędzi na prostej ścieżce między wierzchołkami $u$ a $v$.

Wejście

Pierwszy wiersz zawiera $N$ ($2 \le N \le 100\,000$).

Następne $N-1$ wierszy zawiera po trzy liczby: numery wierzchołków $u$ i $v$ połączonych $i$-tą krawędzią oraz jej koszt $w$.

Kolejny wiersz zawiera liczbę zapytań $M$ ($1 \le M \le 100\,000$).

Następne $M$ wierszy zawiera po jednym zapytaniu w każdym wierszu.

Koszt każdej krawędzi jest liczbą naturalną nie większą niż $1\,000\,000$.

Wyjście

Dla każdego zapytania typu 2 wypisz wyniki w kolejności, każdy w osobnym wierszu.

Przykład

Wejście 1

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

Wyjście 1

1
3