There is a tree (an undirected connected graph with no cycles) consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$.

Write a program that performs the following two types of queries:

• 1 i c: Change the cost of edge $i$ to $c$.
• 2 u v: Output the maximum cost among the edges on the simple path from $u$ to $v$.

Input

The first line contains $N$ ($2 \le N \le 100{,}000$).

The next $N-1$ lines each contain two vertex numbers $u$ and $v$ that edge $i$ connects, and its cost $w$.

The next line contains the number of queries $M$ ($1 \le M \le 100{,}000$).

The next $M$ lines each contain a query.

The cost of each edge is a positive integer not exceeding $1{,}000{,}000$.

Output

For each query of type 2, output the result in order, one per line.

Examples

Input 1

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

Output 1

1
3