Câu Cá Vạn Cân
Xem dạng PDFAi cũng biết, không dùng đến một cây thép ren kết hợp với dây cáp hãm đà tàu sân bay để làm cần câu thì làm sao có thể câu được con quái vật khổng lồ nặng hàng trăm triệu cân.
Mathduck là một người bỏ code để đi câu cá. Vào một ngày đi câu cá trong lễ hội trung thu, ông câu được ~n~ con cá, con cá thứ ~i~ có cân nặng là ~a_i~. Để kết thúc một ngày câu cá hiệu quả, ông quyết định thực hiện ~q~ thao tác, mỗi thao tác thuộc một trong ba loại sau:
1 x: Mathduck câu thêm một con cá có cân nặng ~x~.
2 x: Mathduck bán đi một con cá có cân nặng ~x~. Dữ liệu đảm bảo tồn tại ít nhất một con cá có cân nặng ~x~.
3 w: với mỗi con cá có cân nặng ~x \ge w~, Mathduck cắt bớt để cân nặng của nó còn ~x \bmod w~.
Sau mỗi thao tác, Mathduck cần tính tổng cân nặng của tất cả các con cá mà ông còn giữ.
Input
Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 2 \cdot 10^5~).
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~).
Mỗi dòng trong ~q~ dòng tiếp theo mô tả một thao tác, có dạng 1 x, 2 x hoặc 3 w (~1 \le x, w \le 10^9~).
Output
In ra ~q~ dòng. Dòng thứ ~i~ chứa tổng cân nặng các con cá mà Mathduck còn giữ sau thao tác thứ ~i~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~n, q, a_i, x, w \le 1000~ |
| 2 | ~20~ | Không có truy vấn loại ~3~ |
| 3 | ~20~ | Mọi truy vấn loại ~3~ có ~w \ge \lfloor M / 2 \rfloor~, với ~M~ là giá trị lớn nhất của mảng ~a~ ban đầu |
| 4 | ~40~ | Không có ràng buộc gì thêm |
Sample Input 1
4 5
5 8 12 15
3 6
1 10
3 4
2 2
3 2
Sample Output 1
10
20
8
6
2
Notes
Ban đầu, cân nặng các con cá là ~\{5, 8, 12, 15\}~, tổng là ~40~.
Truy vấn ~1~ (3 6): các con cá nặng ít nhất ~6~ là ~8~, ~12~, ~15~. Ta có ~8 \bmod 6 = 2~, ~12 \bmod 6 = 0~, ~15 \bmod 6 = 3~. Tập mới là ~\{5, 2, 0, 3\}~, tổng là ~10~.
Truy vấn ~2~ (1 10): thêm một con cá nặng ~10~. Tập mới là ~\{5, 2, 0, 3, 10\}~, tổng là ~20~.
Truy vấn ~3~ (3 4): ~5 \bmod 4 = 1~ và ~10 \bmod 4 = 2~. Tập mới là ~\{1, 2, 0, 3, 2\}~, tổng là ~8~.
Truy vấn ~4~ (2 2): bán một con cá nặng ~2~. Tập mới là ~\{1, 0, 3, 2\}~, tổng là ~6~.
Truy vấn ~5~ (3 2): ~3 \bmod 2 = 1~ và ~2 \bmod 2 = 0~. Tập mới là ~\{1, 0, 1, 0\}~, tổng là ~2~.