Một khu vực có ~n~ vị trí, được đánh số từ ~1~ đến ~n~, và ~n-1~ con đường hai chiều nối các vị trí. Mỗi con đường có một độ dài dương. Từ một vị trí bất kỳ luôn có thể đi đến mọi vị trí khác và giữa hai vị trí chỉ có duy nhất một đường đi đơn.

Một số vị trí được đánh dấu là điểm cần kiểm tra. Ban đầu không có vị trí nào được đánh dấu.

Một hành trình tuần tra là một dãy gồm một hoặc nhiều vị trí, trong đó hai vị trí liên tiếp phải được nối trực tiếp bởi một con đường. Một vị trí hoặc một con đường có thể xuất hiện nhiều lần trong hành trình. Độ dài của hành trình là tổng độ dài của các con đường được đi qua, tính cả số lần đi qua mỗi con đường.

Đội tuần tra có thể bắt đầu và kết thúc hành trình tại hai vị trí bất kỳ. Hai vị trí này có thể trùng nhau và không nhất thiết là điểm cần kiểm tra. Hành trình phải đi qua tất cả các điểm cần kiểm tra.

Có ~q~ thao tác. Trong thao tác thứ ~i~, trạng thái của vị trí ~x_i~ được thay đổi:

• Nếu ~x_i~ chưa là điểm cần kiểm tra, nó trở thành điểm cần kiểm tra;

• Nếu ~x_i~ đang là điểm cần kiểm tra, nó không còn là điểm cần kiểm tra.

Sau mỗi thao tác, hãy xác định độ dài nhỏ nhất của một hành trình tuần tra hợp lệ.

Nếu không có điểm cần kiểm tra hoặc chỉ có một điểm cần kiểm tra thì đáp án bằng ~0~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(2 \le n \le 2 \cdot 10^5; 1 \le q \le 2 \cdot 10^5)~;

• Trong ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i, v_i, w_i~, cho biết có một con đường hai chiều nối hai vị trí ~u_i~ và ~v_i~, có độ dài ~w_i~ ~(1 \le u_i, v_i \le n; 1 \le w_i \le 10^9)~;

• Trong ~q~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~x_i~ ~(1 \le x_i \le n)~, mô tả thao tác thay đổi trạng thái của vị trí ~x_i~.

Dữ liệu bảo đảm các con đường tạo thành một cây.

Output

In ra ~q~ dòng. Dòng thứ ~i~ chứa một số nguyên là độ dài nhỏ nhất của hành trình tuần tra sau thao tác thứ ~i~.

Scoring

Sample Input 1

6 8
1 2 3
1 3 2
2 4 4
2 5 1
3 6 5
4
6
5
4
2
6
5
2

Sample Output 1

0
14
16
11
11
1
0
0

Notes

Trạng thái các điểm cần kiểm tra và độ dài hành trình tuần tra nhỏ nhất sau từng thao tác như sau:

• Bật ~4~: tập điểm cần kiểm tra ~\{4\}~; chỉ có một điểm nên không cần di chuyển; độ dài ~0~.

• Bật ~6~: tập điểm cần kiểm tra ~\{4, 6\}~; một hành trình tối ưu là ~4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6~, có độ dài ~= 4 + 3 + 2 + 5 = 14~.

• Bật ~5~: tập điểm cần kiểm tra ~\{4, 5, 6\}~; một hành trình tối ưu là ~4 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6~, có độ dài ~= 4 + 1 + 1 + 3 + 2 + 5 = 16~.

• Tắt ~4~: tập điểm cần kiểm tra ~\{5, 6\}~; một hành trình tối ưu là ~5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6~, có độ dài ~= 1 + 3 + 2 + 5 = 11~.

• Bật ~2~: tập điểm cần kiểm tra ~\{2, 5, 6\}~; điểm ~2~ nằm trên đường đi từ ~5~ đến ~6~ nên một hành trình tối ưu vẫn là ~5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6~, độ dài ~11~.

• Tắt ~6~: tập điểm cần kiểm tra ~\{2, 5\}~; một hành trình tối ưu là ~2 \rightarrow 5~, độ dài ~1~.

• Tắt ~5~: tập điểm cần kiểm tra ~\{2\}~; chỉ có một điểm nên không cần di chuyển; độ dài ~0~.

• Tắt ~2~: không còn điểm cần kiểm tra nào; không cần di chuyển; độ dài ~0~.

Vì vậy, tám kết quả lần lượt là ~0, 14, 16, 11, 11, 1, 0, 0~.