Bảng băm và va chạm

Một bảng băm gồm $h$ ô được đánh số từ $0$ đến $h-1$. Mỗi đối tượng có một định danh id duy nhất và một giá trị băm hash nằm trong đoạn $[0,h-1]$.

Khi thêm một đối tượng có giá trị băm $t$ vào bảng, ta thử đặt nó vào ô $t$. Nếu ô $t$ đã bị chiếm, ta thử ô $(t+m)modh$, rồi $(t+2m)modh$, rồi $(t+3m)modh$, và cứ thế tiếp tục cho tới khi gặp một ô trống. Đối tượng được đặt vào ô trống đầu tiên tìm được.

Nếu đối tượng cuối cùng được đặt vào ô $(t+i·m)modh$ với $i\ge 0$, thì đã có đúng $i$ lần truy cập vô ích (các lần chạm vào ô đã bị chiếm).

Khi xoá một đối tượng khỏi bảng, ô mà nó đang chiếm trở lại trạng thái trống. Thao tác xoá không tính lần truy cập vô ích nào.

Cho một dãy $n$ thao tác thêm và xoá, hãy tính tổng số lần truy cập vô ích. Ban đầu bảng rỗng.

Dữ liệu bảo đảm mọi thao tác thêm đều đặt được đối tượng vào bảng, mọi id của thao tác thêm là phân biệt, và không có thao tác xoá đối tượng không tồn tại.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $h$, $m$, $n$: kích thước bảng, bước dò tuyến tính và số thao tác.
• $n$ dòng tiếp theo, mỗi dòng mô tả một thao tác:
  • + id hash — thêm đối tượng có định danh id và giá trị băm hash.
  • - id — xoá đối tượng có định danh id.

Dữ liệu ra

Một số nguyên duy nhất: tổng số lần truy cập vô ích.

Ràng buộc

• $1\le m<h\le 2·{10}^5$
• $1\le n\le 2·{10}^5$
• $0\le id\le {10}^9$
• $0\le hash<h$

Ví dụ