You are given a weighted tree with $n$ vertices and edges $(u_1, v_1)$ with weight $w_1$, $(u_2, v_2)$ with weight $w_2$, ..., $(u_{n-1}, v_{n-1})$ with weight $w_{n-1}$. Write a program longest that supports $q$ queries of 2 types:

• $1, x, k, n_1, \dots, n_k$, find the length of the longest path from $x$ to any vertex $y$ such that the path from $x$ to $y$ does not pass through any vertex in the set $\{n_1, \dots, n_k\}$.
• $2, i, w$, the weight of the $i$-th edge $(u_i, v_i)$ is changed to $w$.

Input

The first line of standard input contains the integer $n$. The next $n-1$ lines contain 3 integers $u_i, v_i, w_i$, representing an edge between vertices $u_i$ and $v_i$ with weight $w_i$. The next line contains the integer $q$. Each of the next $q$ lines first contains the query type, 1 or 2. If the type is 1, the integers $x, k$ are entered, followed by $k$ integers $n_1, \dots, n_k$. If the type is 2, the integers $i$ and $w$ are entered.

Output

For each query of type 1, print the requested length to standard output.

Constraints

• $1 \le n, q, \sum k \le 200000$
• $1 \le u_i, v_i \le n$
• $1 \le w, w_i \le 10^9$
• $n_j \neq x$ for all $1 \le j \le k$
• $n_i \neq n_j$ for all $1 \le i \neq j \le k$

Subtasks

Points for a given subtask are awarded only if all test cases for that subtask are passed successfully.

Examples

Input 1

5
1 2 1
1 4 2
2 3 3
2 5 4
10
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 1 1 5
1 1 1 2
2 1 100
1 2 0
1 2 4 1 3 4 5

Output 1

5
4
7
7
7
4
2
102
0

Note 1

The target vertices in the queries are 5, 5, 5, 5, 3, 3, 4, 4, 2 respectively.