Ông Già Noel

Dạng bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 1000M Input: bàn phím Output: màn hình

Một nhóm tuần lộc được chọn để kéo xe trượt tuyết. Mỗi con tuần lộc có một tên (chuỗi ký tự, \(\le 20\) chữ cái, phân biệt chữ hoa/thường), một thâm niên và một năng suất (cả hai là số nguyên dương \(\le 10^6\)).

Khi kéo xe, chúng xếp thành một hàng, luôn theo thứ tự thâm niên giảm dần từ trước ra sau. (Đề bài đảm bảo không có hai con tuần lộc nào có cùng thâm niên).

Năng suất của một cặp tuần lộc liền kề trong hàng là tích của hai năng suất cá nhân của chúng.
Tổng năng suất của cả hàng là tổng năng suất của tất cả các cặp liền kề.
(Nếu hàng có 0 hoặc 1 con, tổng năng suất là 0).

Ban đầu hàng trống. Santa sẽ thực hiện \(M\) (\(1 \le M \le 10^5\)) thao tác:

A name S P: Thêm một con tuần lộc mới (tên name, thâm niên \(S\), năng suất \(P\)) vào hàng. Nó sẽ được chèn vào vị trí chính xác để duy trì thứ tự thâm niên giảm dần. (Đảm bảo mỗi con chỉ được thêm 1 lần).
R name: Xóa con tuần lộc có tên name khỏi hàng. (Đảm bảo con này đang có trong hàng).

Bạn cần tính và in ra tổng năng suất của hàng sau mỗi thao tác.

Input

Dòng đầu tiên chứa số nguyên \(M\).
\(M\) dòng tiếp theo, mỗi dòng là một thao tác có dạng A name S P hoặc R name.

Output

In ra \(M\) dòng. Dòng thứ \(i\) là tổng năng suất của hàng sau thao tác thứ \(i\).

Examples

Test 1

Input

5
A Dancer 5 2
A Prancer 3 8
A Vixen 10 9
R Dancer
A Rudolph 1 1

Output

Explanation

(Hàng được sắp xếp theo thâm niên (S) giảm dần)

A Dancer 5 2: Hàng: [Dancer(S=5, P=2)]. Chỉ có 1 con. Tổng = 0.
A Prancer 3 8: Hàng: [Dancer(S=5, P=2), Prancer(S=3, P=8)]. Tổng = \(2 \times 8 = 16\).
A Vixen 10 9: Hàng: [Vixen(S=10, P=9), Dancer(S=5, P=2), Prancer(S=3, P=8)].
Tổng = \((9 \times 2) + (2 \times 8) = 18 + 16 = 34\).
R Dancer: Hàng: [Vixen(S=10, P=9), Prancer(S=3, P=8)].
Tổng = \(9 \times 8 = 72\).
A Rudolph 1 1: Hàng: [Vixen(S=10, P=9), Prancer(S=3, P=8), Rudolph(S=1, P=1)].
Tổng = \((9 \times 8) + (8 \times 1) = 72 + 8 = 80\).

Bình luận

Không có bình luận nào.