$N$ 个顶点构成一棵树。顶点编号为 $0$ 到 $N-1$。每条边有一个非负整数权值。

需要执行以下查询：

• 1 u v w x：删除连接 $u$ 和 $v$ 的边，然后添加一条连接 $v$ 和 $w$、权值为 $x$ 的边。保证存在连接 $u$ 和 $v$ 的边。执行操作后，图仍然是一棵树。($0 \le x \le 100\,000$)
• 2 k x_1 x_2 ... x_k：考虑顶点 $x_1, x_2, \ldots, x_k$，对于所有 $1 \le i < j \le k$，考虑连接 $x_i$ 和 $x_j$ 的唯一简单路径。输出这些简单路径的边集并集中所有边的权值之和。所有 $x_i$ 互不相同。($1 \le k \le n$)

输入格式

第一行包含树的规模 $N$。($2 \le N \le 100{,}000$)

接下来 $N-1$ 行，每行三个整数 $u, v, w$，表示存在一条连接顶点 $u$ 和 $v$、权值为 $w$ 的边。($0 \le u, v \le N - 1$, $0 \le w \le 100{,}000$)

下一行包含查询的个数 $Q$。($1 \le Q \le 100{,}000$)

接下来 $Q$ 行，每行一个上述格式的查询。

所有 $2$ 号查询的 $k$ 之和介于 $1$ 和 $100{,}000$ 之间（含两端）。

输出格式

按顺序输出每个 $2$ 号查询的结果，每个结果占一行。

样例

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

样例输出 1

20
27