Công ty viễn thông FPT đang vận hành cơ sở hạ tầng mạng gồm \(N\) điểm truy cập. Các tuyến cáp quang có thể được lắp đặt hoặc tháo dỡ theo kế hoạch.

Để tối ưu chi phí vận hành, công ty cần biết tổng chi phí nhỏ nhất để kết nối toàn bộ mạng lưới (cây khung nhỏ nhất — MST) sau mỗi lần thay đổi.

Đồ thị có trọng số \(N\) đỉnh, ban đầu không có cạnh nào. Hệ thống nhận \(Q\) thao tác:

• add u v w — Lắp đặt tuyến cáp \((u, v)\) với chi phí \(w\) (đảm bảo tuyến chưa tồn tại).
• remove u v — Tháo dỡ tuyến cáp \((u, v)\) (đảm bảo tuyến đang tồn tại).
• query — In tổng trọng số MST. Nếu mạng lưới không liên thông, in \(-1\).

Gợi ý: Xác định khoảng thời gian tồn tại của từng cạnh, sau đó áp dụng D&C trên thời gian + DSU Rollback để duy trì MST động.

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và \(Q\) (\(1 \le N \le 10^4\), \(1 \le Q \le 5 \times 10^4\)).
• \(Q\) dòng tiếp theo, mỗi dòng là một thao tác.

Định dạng đầu ra

Với mỗi thao tác query, in một số nguyên — tổng trọng số MST, hoặc \(-1\) nếu không liên thông.

Ví dụ

Input:

3 7
add 1 2 4
add 2 3 3
add 1 3 2
query
remove 2 3
query
remove 1 2

Output:

5
6

Giải thích:

• Thêm cạnh 1–2 (w=4), 2–3 (w=3), 1–3 (w=2): ba cạnh nối đủ 3 đỉnh.
• query: MST chọn 2 cạnh nhỏ nhất nối 3 đỉnh = {1–3 (2), 2–3 (3)} = 5.
• Xóa 2–3: còn cạnh 1–2 (4) và 1–3 (2). MST = {1–3 (2), 1–2 (4)} = 6.
• Xóa 1–2: còn cạnh 1–3 (2). Đỉnh 2 không có cạnh → không liên thông (sẽ in \(-1\) nếu có query).

Ràng buộc

\(1 \le u, v \le N\), \(u \ne v\), \(1 \le w \le 10^9\).