Trang trại JOI nhập và xuất táo. Táo được nhập từng quả một. Khi có yêu cầu xuất hàng, trang trại phải xử lý ngay, không đợi lần nhập táo tiếp theo. Mỗi yêu cầu xuất hàng chỉ định số táo cần xuất. Nếu có thể chọn đúng số táo đó theo quy định của trang trại, trang trại lập tức xuất những quả táo đã chọn. Nếu không thể, trang trại thông báo rằng không thể xuất hàng và không xuất quả táo nào.

Năm nay, trang trại JOI dự kiến sẽ nhập rất nhiều táo và nhận rất nhiều yêu cầu xuất hàng. Bạn được nhờ viết chương trình quản lý táo cho trang trại.

Yêu cầu

Mỗi quả táo có một độ đậm màu là số nguyên. Độ chênh lệch màu của một lần xuất hàng là hiệu giữa độ đậm màu lớn nhất và nhỏ nhất trong số táo được xuất. Quy định của trang trại yêu cầu độ chênh lệch này không vượt quá \(B\).

Chương trình nhận tổng cộng \(M\) yêu cầu. Yêu cầu thứ \(i\) thuộc một trong ba loại sau:

• Nhập táo: nhận thông tin rằng một quả táo có độ đậm màu \(D_i\) vừa được nhập và ghi nhận quả táo đó.
• Xuất hàng: nhận yêu cầu xuất \(N_i\) quả táo. Nếu có thể xuất hàng, in độ đậm màu của từng quả táo được xuất theo thứ tự tăng dần. Nếu không thể, in NO. Khi có nhiều cách chọn hợp lệ, phải chọn cách có tổng độ đậm màu lớn nhất. Những quả đã xuất không còn ở trang trại.
• Kết thúc chương trình: kết thúc chương trình khi nhận lệnh này.

Giao thức tương tác

Đây là bài tương tác (Reactive task) qua đầu vào chuẩn và đầu ra chuẩn. Nếu yêu cầu thứ \(i\) là yêu cầu xuất hàng, dữ liệu của yêu cầu thứ \(i+1\) chỉ được cung cấp sau khi chương trình đã xuất câu trả lời cho yêu cầu thứ \(i\).

Cần bảo đảm dữ liệu xuất không bị giữ trong bộ đệm, khiến thao tác đọc tiếp theo bị chặn. Gọi fflush(stdout); hoặc thực hiện thao tác tương đương trước khi đọc dữ liệu tiếp theo.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo giao thức trên:

• Dòng đầu chứa hai số nguyên \(M,B\), cách nhau bởi một dấu cách: tổng số yêu cầu và giới hạn độ chênh lệch màu của mỗi lần xuất hàng.
• Dòng thứ \(i+1\) \((1\le i\le M-1)\) chứa một yêu cầu nhập táo hoặc xuất hàng. Yêu cầu nhập táo có dạng A D_i, trong đó \(D_i\) là độ đậm màu của quả táo vừa nhập. Yêu cầu xuất hàng có dạng R N_i, trong đó \(N_i\) là số táo cần xuất. Chữ cái và số nguyên được ngăn cách bằng một dấu cách.
• Dòng thứ \(M+1\) chỉ chứa ký tự E, là yêu cầu kết thúc chương trình. Lệnh này được tính trong tổng số \(M\) yêu cầu.

Dữ liệu ra

Mỗi khi nhận yêu cầu xuất hàng, nếu không thể đáp ứng thì in một dòng chứa NO. Nếu có thể, in một dòng chứa độ đậm màu của tất cả các quả táo được xuất theo thứ tự tăng dần, cách nhau bởi dấu cách. Phải chọn cách xuất có tổng độ đậm màu lớn nhất trong các cách đáp ứng quy định.

Ràng buộc

• \(1\le M\le100\,000\).
• \(0\le B\le1\,000\,000\,000\).
• \(0\le D_i\le1\,000\,000\,000\) với các yêu cầu nhập táo, \(1\le i\le M\).
• \(1\le N_i\le100\,000\) với các yêu cầu xuất hàng, \(1\le i\le M\).

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(4\) giây, bộ nhớ \(256\) MB. Riêng bài này, thời gian được tính bằng tổng thời gian chạy của chương trình thí sinh và chương trình chấm. Nếu chương trình thí sinh sử dụng từ \(1\) giây trở lên, bài nộp có thể bị quá thời gian.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn đồng thời \(B\le10\,000\) và \(D_i\le10\,000\) với mọi yêu cầu nhập táo.

Ví dụ giao tiếp

Bảng sau giữ thứ tự nhận dữ liệu và xuất câu trả lời trong ví dụ. Cột Dữ liệu vào là dữ liệu hệ thống gửi cho chương trình; cột Dữ liệu ra là câu trả lời của chương trình. Ô trống nghĩa là không có dữ liệu ở phía đó trong bước tương ứng.