$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