题目描述

给定一棵带权树，包含 $n$ 个顶点，边 $(u_1, v_1)$ 的长度为 $w_1$，$(u_2, v_2)$ 的长度为 $w_2$，...，$(u_{n-1}, v_{n-1})$ 的长度为 $w_{n-1}$。请编写一个程序 longest，支持以下两种类型的查询：

• $1, x, k, n_1, \dots, n_k$，求从顶点 $x$ 到任意顶点 $y$ 的最长路径长度，使得从 $x$ 到 $y$ 的路径不经过 $\{n_1, \dots, n_k\}$ 中的任何顶点。
• $2, i, w$，将第 $i$ 条边的长度修改为 $w$。

输入格式

输入的第一行包含一个整数 $n$。接下来的 $n-1$ 行，每行包含 3 个整数 $u_i, v_i, w_i$，表示顶点 $u_i$ 和 $v_i$ 之间有一条长度为 $w_i$ 的边。下一行包含一个整数 $q$。接下来的 $q$ 行，每行首先输入查询类型（1 或 2）。如果类型为 1，则输入 $x, k$ 以及 $k$ 个整数 $n_1, \dots, n_k$。如果类型为 2，则输入 $i$ 和 $w$。

输出格式

对于每个类型为 1 的查询，在标准输出中打印所求的最长路径长度。

数据范围

• $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_i \neq x$ 对于所有 $1 \le i \le k$
• $n_i \neq n_j$ 对于所有 $1 \le i \neq j \le k$

子任务

样例

输入 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

输出 1

5
4
7
7
7
4
2
102
0

说明 1

查询中对应的目标顶点分别为 5, 5, 5, 5, 3, 3, 4, 4, 2。