Có một cây gồm $N$ đỉnh. Các đỉnh được đánh số từ $0$ đến $N-1$. Các cạnh có trọng số nguyên không âm.

Cần thực hiện các truy vấn sau:

• 1 u v w x: Loại bỏ cạnh nối $u$ và $v$, sau đó thêm cạnh nối $v$ và $w$ với trọng số $x$. Dữ liệu đảm bảo tồn tại cạnh nối $u$ và $v$. Sau khi thực hiện thao tác, đồ thị vẫn là một cây. ($0 \le x \le 100\,000$)
• 2 k x_1 x_2 ... x_k: Với các đỉnh $x_1, x_2, \ldots, x_k$, xét tất cả các đường đi đơn duy nhất nối $x_i$ và $x_j$ với mọi $1 \le i < j \le k$. Hãy tính tổng trọng số của tất cả các cạnh thuộc hợp của các đường đi đơn này. Tất cả $x_i$ đôi một khác nhau. ($1 \le k \le n$)

Dữ liệu vào

Dòng đầu tiên chứa kích thước của cây $N$ ($2 \le N \le 100{,}000$).

$N-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ — có một cạnh nối hai đỉnh $u$ và $v$ với trọng số $w$ ($0 \le u, v \le N - 1$, $0 \le w \le 100{,}000$).

Dòng tiếp theo chứa số lượng truy vấn $Q$ ($1 \le Q \le 100{,}000$).

$Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn như mô tả ở trên.

Tổng các $k$ trong các truy vấn loại $2$ nằm trong khoảng từ $1$ đến $100{,}000$.

Dữ liệu ra

Với mỗi truy vấn loại $2$, in ra kết quả trên một dòng theo thứ tự.

Ví dụ

Đầu vào 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

Đầu ra 1

20
27