There is a tree consisting of $N$ vertices. The vertices are numbered from $0$ to $N-1$. The edges have non‑negative integer weights.

You need to process the following queries.

1. 1 u v w x: Remove the edge connecting $u$ and $v$, and add an edge of weight $x$ connecting $v$ and $w$. It is guaranteed that there exists an edge between $u$ and $v$. After the operation, the graph remains a tree. ($0 \le x \le 100\,000$)
2. 2 k x_1 x_2 ... x_k: For the vertices $x_1, x_2, \ldots, x_k$, consider all unique simple paths between every pair $x_i$ and $x_j$ (for all $1 \le i < j \le k$). Output the sum of weights of all edges that belong to the union of these paths. All $x_i$ are distinct. ($1 \le k \le n$)

Input

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

The next $N-1$ lines each contain three integers $u, v, w$, denoting an edge of weight $w$ connecting vertices $u$ and $v$. ($0 \le u, v \le N - 1$, $0 \le w \le 100{,}000$)

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

The following $Q$ lines contain queries as described above.

The sum of $k$ over all type 2 queries is between $1$ and $100{,}000$ inclusive.

Output

For each type 2 query, output the result on a separate line, in order.

Examples

Input 1

7
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
2 6 6
4
1 1 4 5 7
2 3 0 4 6
1 0 2 1 8
2 3 0 4 6

Output 1

20
27