题目描述

给定一棵带权树，共有 $n$ 个点。

第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，边长为 $w_i$。

请你编写程序 longest，支持 $q$ 次操作，操作分为两种类型：

• 1 x k n_1 ... n_k：求从顶点 $x$ 到某个顶点 $y$ 的最长路径长度，要求从 $x$ 到 $y$ 的路径不能经过顶点 $n_1, n_2, \dots, n_k$ 中的任何一个。
• 2 i w：将第 $i$ 条边 $(u_i, v_i)$ 的长度修改为 $w$。

对于每个第一类操作，输出所求的最长路径长度。

输入格式

第一行一个整数 $n$，表示树的节点数。

接下来 $n-1$ 行，每行三个整数 $u_i, v_i, w_i$，表示一条连接 $u_i$ 与 $v_i$ 的边，边长为 $w_i$。

接下来一行一个整数 $q$，表示操作数。

接下来 $q$ 行，每行描述一个操作。

• 如果操作类型为 1，则输入格式为：

  1 x k n_1 n_2 ... n_k

• 如果操作类型为 2，则输入格式为：

  2 i w

输出格式

对于每个类型为 1 的操作，输出一行一个整数，表示答案。

数据范围

• $1 \le n, q, \sum k \le 200000$
• $1 \le u_i, v_i \le n$
• $1 \le w_i, w \le 10^9$
• 对于任意 $1 \le i \le k$，有 $n_i \ne x$
• 对于任意 $1 \le i \ne j \le k$，有 $n_i \ne n_j$

子任务

只有通过某个子任务的全部测试点，才能获得该子任务的分数。

样例输入

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

样例输出

5
4
7
7
7
4
2
102
0

样例说明

上述若干次第一类询问中，满足条件的目标点 $y$ 依次为：

$5, 5, 5, 5, 3, 3, 4, 4, 2$。