Cho đồ thị ~G~ gồm ~n~ đỉnh, một số đỉnh có thể được kết nối bằng các cạnh. Các cạnh của đồ thị sẽ được biểu diễn bằng các màu sắc khác nhau thông qua các số nguyên từ ~1~ đến ~10^5~.

Đồ thị ~G~ được xây dựng như sau: ban đầu, đồ thị có ~n~ đỉnh và không có cạnh, sau đó ~q~ truy vấn được thực hiện.

• + ~v~ ~u~ ~c~: thêm một cạnh ~(v, u)~ có màu ~c~ vào đồ thị. Đảm bảo rằng không có cạnh nào có màu ~c~ giữa các đỉnh ~v~ và ~u~.

• - ~v~ ~u~ ~c~: xóa cạnh ~(v, u)~ có màu ~c~ khỏi đồ thị. Đảm bảo rằng có một cạnh có màu ~c~ giữa các đỉnh ~u~ và ~v~.

Màu ~c~ trong đồ thị là màu đẹp nếu không có nhiều hơn một cạnh của màu đó được kết nối với mỗi đỉnh. Giá trị vẻ đẹp của màu ~c~ là số cạnh của màu đó.

Sau mỗi truy vấn, giá trị vẻ đẹp của đồ thị là tổng giá trị vẻ đẹp của các màu đẹp.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ tương ứng số đỉnh của đồ thị và số truy vấn ~(2 \le n \le 10^5, 1 \le q \le 10^5)~.

~q~ dòng tiếp theo mô tả các truy vấn ~(1 \le v, u \le n; v \ne u; 1 \le c \le 10^5)~.

Output

In ra ~q~ dòng, với mỗi dòng bạn cần đưa ra tổng giá trị vẻ đẹp của đồ thị của mỗi truy vấn.

Sample Input 1

4 5
+ 1 2 1
+ 3 4 2
+ 2 4 1
- 2 1 1
+ 2 4 4

Sample Output 1

1
2
1
2
3