Phần mềm thu ngân

Hoàng sinh viên năm 2 ngành Kỹ sư Công nghệ thông tin là một trong những ngành đang được ưa chuộng nhất hiện nay chuyên ngành kỹ thuật phần mềm trường Đại Học Bách Khoa. Hè đến rồi, để củng cố các kiến thức mà mình đã học. Hoàng quyết định sẽ đi làm thêm giúp đỡ bố mẹ, công việc mà Hoàng chọn là lập trình phần mềm Thu ngân cho một quán café gần nhà. Để hoàn thiện được các chức năng của phần mềm Hoàng dạo phố trải nghiệm hoạt động của một quán café truyền thống với công việc kế toán, trong đó có 4 thao tác:

• \(I\ K\): Thêm một nhân viên mới với mức lương ban đầu là \(K\).

• \(A\ K\): Tăng lương tất cả nhân viên trong quán lên \(K\) đơn vị.

• \(S\ K\): Giảm lương tất cả nhân viên trong quán xuống \(K\) đơn vị.

• \(F\ k\): Tìm và in ra lương của nhân viên có lương cao thứ \(k\) trong toàn bộ nhân viên của quán.

Ngoài ra, có các điều kiện cho các thao tác:

• Số lượng thao tác \(I\) và \(F\) không vượt quá \(10^{5}\).

• Số lượng thao tác A và S không vượt quá 100.

• Thao tác A và S có điều kiện thỏa mãn: \(K \leq 1000.\)

• Thao tác I có điều kiện thỏa mãn: \(K \leq 10^{5}.\)

• Thao tác F có điều kiện thỏa mãn: \(k \leq 10^{5}.\)

Tuy nhiên, chúng ta đều biết con người làm việc để duy trì sự sống, và với mức lương quá thấp, họ sẽ không thể tiếp tục làm. Trong quán café này cũng vậy. Bất cứ nhân viên nào có số lương thấp hơn \(X\) sẽ đi tìm những công việc khác do đãi ngộ tốt hơn.

Qua thực tế Hoàng đã nắm được các công việc mà mình cần hoàn thiện phần mềm. Hãy cho biết với mỗi thao tác \(F\) , đáp án sẽ là bao nhiêu. Ngoài ra, Hoàng cần tính số lượng nhân viên nghỉ việc sau toàn bộ thao tác.

Yêu cầu: Với mỗi thao tác \(F\ k\), in ra đáp án cần tìm. Nếu số lượng nhân viên ít hơn 𝑘, in ra -1. Cho biết số lượng nhân viên nghỉ việc sau toàn bộ thao tác.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên dương \(N\) và \(X\ (1 \leq N,X \leq 10^{5})\) là số lượng thao tác và mức lương tối thiểu nhân viên chấp nhận làm việc.

+ \(N\) dòng tiếp theo, mỗi dòng gồm một thao tác như đã được miêu tả ở trên.

Kết quả:

Với mỗi thao tác \(F\), in ra đáp án là một dòng tương ứng.

Dòng cuối cùng là số lượng nhân viên nghỉ việc sau toàn bộ thao tác.

Ví dụ:

Input	Output
9 10 I 60 I 70 S 50 F 2 I 30 S 15 A 5 F 1 F 2	10 20 -1 2

Giải thích:

Sau 2 thao tác đầu, có 2 nhân viên hưởng 60 và 70 lương. Thao tác 3 giảm lương nhân viên 10 và 20. Nhân viên có mức lương cao thứ 2 bây giờ là 10. Sau tất cả các thao tác, có tổng cộng 2 nhân viên nghỉ việc.

Ràng buộc:

Subtask 1: Có 30% số test thỏa mãn: \(N\ \leq \ 1000\).

Subtask 2: Có 20% số test thỏa mãn: Không có thao tác \(F\).

Subtask 3: Có 20% số test thỏa mãn: Không có thao tác \(A\) và \(S\).

Subtask 4: Có 30% số test thỏa mãn: Không có ràng buộc gì thêm.