Problem Statement

You are given a tree $T$ with $N$ vertices. Edge $i$ $(1\leq i\leq N-1)$ connects vertices $u _ i$ and $v _ i$, and has a weight of $w _ i$.

Process $Q$ queries in order. There are two kinds of queries as follows.

• 1 i w : Change the weight of edge $i$ to $w$.
• 2 u v：Print the distance between vertex $u$ and vertex $v$.

Here, the distance between two vertices $u$ and $v$ of a tree is the smallest total weight of edges in a path whose endpoints are $u$ and $v$.

Constraints

• $1\leq N\leq 2\times10^5$
• $1\leq u _ i,v _ i\leq N\ (1\leq i\leq N-1)$
• $1\leq w _ i\leq 10^9\ (1\leq i\leq N-1)$
• The given graph is a tree.
• $1\leq Q\leq 2\times10^5$
• For each query of the first kind,
• $1\leq i\leq N-1$, and
  • $1\leq w\leq 10^9$.
• For each query of the second kind,
• $1\leq u,v\leq N$.
• There is at least one query of the second kind.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
u _ 1 v _ 1 w _ 1
u _ 2 v _ 2 w _ 2
\vdots
u _ {N-1} v _ {N-1} w _ {N-1}
Q
\operatorname{query} _ 1
\operatorname{query} _ 2
\vdots
\operatorname{query} _ Q

Here, $\operatorname{query} _ i$ denotes the $i$-th query and is in one of the following format:

1 i w

2 u v

Output

Print $q$ lines, where $q$ is the number of queries of the second kind. The $j$-th line $(1\leq j\leq q)$ should contain the answer to the $j$-th query of the second kind.