Siêu Sức Mạnh

Một đội gồm N thành viên tham gia chiến dịch tấn công Vương quốc Gà; mỗi thành viên có một giá trị sức mạnh đại diện cho khả năng chiến đấu của mình. Khi một thành viên sử dụng buff thiên sứ X cho cả đội, sức mạnh của mỗi thành viên sẽ tăng thêm X. Khi Vua Gà ném lựu đạn X, sức mạnh của mỗi thành viên sẽ giảm đi X.

Đội trưởng sở hữu Siêu Sức Mạnh (Super Power) có thể hợp nhất sức mạnh của cả đội — được tính bằng tổng các giá trị tuyệt đối sức mạnh của từng thành viên — để tung ra một đòn tấn công cực mạnh lên Vua Gà. Trong suốt trận chiến, có Q lần giá trị sức mạnh của đội thay đổi khi một thành viên sử dụng buff thiên sứ hoặc Vua Gà ném lựu đạn. Do số lần sử dụng Super Power có hạn, hãy giúp đội trưởng tính toán giá trị Super Power từ lúc bắt đầu cho đến khi kết thúc trận chiến để đưa ra quyết định tối ưu nhất.

Đầu vào:

• Dòng đầu tiên chứa số nguyên N $(1 \le N \le 2 \times 10^{5})$ — số lượng thành viên của đội — và số nguyên Q $(1 \le Q \le 2 \times 10^{5})$ — số lượt thay đổi sức mạnh.
• Dòng tiếp theo chứa N số nguyên a_i $(|a_i| \le 5000)$ — sức mạnh ban đầu của từng thành viên.
• Q dòng tiếp theo, mỗi dòng chứa một ký tự (B biểu thị một thành viên sử dụng buff thiên sứ hoặc D biểu thị Vua Gà ném lựu đạn) và một số nguyên X $(0 \le X \le 5000)$ — giá trị thay đổi X — phân tách nhau bởi một dấu cách.

Đầu ra: In ra $Q + 1$ dòng: dòng đầu tiên là sức mạnh ban đầu của đội và Q dòng tiếp theo là sức mạnh của đội sau mỗi lượt trong Q lượt thay đổi.

Giải thích:

• Ban đầu, sức mạnh của đội là $|-1|+0+2+|-3|=6$.
• Lần thay đổi 1: Sức mạnh của từng thành viên là $[-2, -1, 1, -4]$. Sức mạnh của đội là $|-2|+|-1|+1+|-4|=8$.
• Lần thay đổi 2: Sức mạnh của từng thành viên là $[0, 1, 3, -2]$. Sức mạnh của đội là $0+1+3+|-2|=6$.
• Lần thay đổi 3: Sức mạnh của từng thành viên là $[-3, -2, 0, -5]$. Sức mạnh của đội là $|-3|+|-2|+0+|-5|=10$.

Ví dụ 1:

Đầu vào:

4 3
-1 0 2 -3
D 1
B 2
D 3

Đầu ra:

6
8
6
10