Vinh quang bất diệt thuộc về những ai giành được huy chương BOI. Bạn cũng muốn trở thành một trong số họ, và con đường dành cho bạn là luyện tập, luyện tập, rồi lại luyện tập! “Có thật vậy không?”, một giọng nói nhỏ trong đầu bạn khẽ hỏi.

Bước đầu tiên trong kế hoạch luyện tập là mua một số sách khoa học máy tính. May mắn thay, hiệu sách gần nhà đang giảm giá rất nhiều nếu bạn mua đúng \(K\) quyển.

Bạn cần chọn \(K\) quyển trong số \(N\) quyển sách khoa học máy tính được bán tại cửa hàng, đánh số từ \(1\) đến \(N\). Tiêu chí lựa chọn chính của bạn là độ khó: mỗi quyển sách \(i\) có một độ khó riêng, hoàn toàn khách quan, là \(x_i\); tổng độ khó của một tập sách bằng tổng độ khó của từng quyển trong tập đó. Bạn không muốn sách quá dễ, vì như vậy sẽ không học đủ để giành huy chương quý giá, cũng không muốn sách quá khó, vì sẽ không kịp hiểu trước khi cuộc thi bắt đầu. Cụ thể, tổng độ khó của những quyển sách được chọn phải ít nhất là \(A\) và không quá \(2A\).

Muốn biết độ khó thực sự của một quyển sách, bạn phải đọc lướt qua nó. Nhưng chủ hiệu sách sẽ không vui nếu bạn đọc quá nhiều mà không mua, nên cô ấy chỉ cho phép bạn đọc lướt nhiều nhất \(S\) quyển. May thay, cô ấy cũng cho biết sách đã được sắp xếp theo độ khó tăng dần.

Hãy viết chương trình giúp bạn quyết định những quyển sách cần đọc lướt, rồi cuối cùng chỉ ra những quyển cần mua.

Giao tiếp

Đây là bài toán giao tiếp. Bạn phải cài đặt hàm sau:

void solve(int N, int K, long long A, int S);

Các tham số \(N\), \(K\), \(A\) và \(S\) có ý nghĩa như trên. Các độ khó \(x_1<x_2<\cdots<x_N\) ban đầu được giữ bí mật với chương trình. Với mỗi bộ dữ liệu, trình chấm gọi solve đúng một lần. Trong hàm này, bạn có thể gọi các hàm sau do trình chấm cung cấp:

long long skim(int i);
void answer(std::vector<int> v);
void impossible();

• skim(i) đọc lướt quyển sách thứ \(i\) và trả về độ khó \(x_i\), với \(1\le i\le N\).
• answer(v) mua những quyển sách bạn chọn. Phải truyền \(v=\{i_1,\ldots,i_K\}\), trong đó \(1\le i_1,\ldots,i_K\le N\), các chỉ số \(i_j\) đôi một khác nhau và \(A\le x_{i_1}+\cdots+x_{i_K}\le2A\).
• impossible() khẳng định rằng không thể chọn một tập gồm \(K\) quyển sách có tổng độ khó mong muốn.

Nếu tồn tại một cách chọn hợp lệ, bạn phải gọi answer đúng một lần. Nếu không, bạn phải gọi impossible đúng một lần. Chương trình tự động kết thúc sau khi gọi một trong hai hàm này.

Nếu bất kỳ lời gọi hàm nào không đúng định dạng trên, hoặc nếu bạn gọi skim quá \(S\) lần, chương trình lập tức bị kết thúc và nhận kết quả Not correct cho bộ dữ liệu đó. Không được ghi bất cứ thứ gì ra đầu ra chuẩn; nếu vi phạm, bạn có thể nhận kết quả Security violation!.

Nếu dùng C++, mã nguồn phải có #include "books.h". Để chạy thử trên máy, bạn có thể liên kết chương trình với sample_grader.cpp, được cung cấp trong phần đính kèm của bài trên CMS chính thức. Phần đính kèm còn có tệp cài đặt mẫu books_sample.cpp với các giải thích bổ sung. Nếu dùng Python, tệp mẫu books_sample.py trong phần đính kèm mô tả giao diện dành cho bài nộp Python.

Dữ liệu vào

Bài nộp nhận \(N\), \(K\), \(A\) và \(S\) qua tham số của solve, còn độ khó của từng quyển sách được truy vấn bằng skim.

Trình chấm mẫu nhận hai dòng từ đầu vào chuẩn. Dòng đầu chứa bốn số nguyên \(N\), \(K\), \(A\) và \(S\). Dòng thứ hai chứa \(N\) số nguyên \(x_1,x_2,\ldots,x_N\), là dãy độ khó tăng nghiêm ngặt.

Dữ liệu ra

Bài nộp đưa ra kết quả bằng answer hoặc impossible, không ghi ra đầu ra chuẩn.

Trình chấm mẫu ghi nhật ký tất cả các lời gọi hàm do chương trình thực hiện ra đầu ra chuẩn. Cuối cùng, nó ghi một trong các thông báo được mô tả trong phần “Trình chấm mẫu” dưới đây.

Ràng buộc

• \(K\le N\).
• \(3\le N,S\le10^5\).
• \(1\le A,x_i\le10^{17}\).
• \(3\le K\le10\).
• \(x_1<x_2<\cdots<x_N\).

Phân nhóm

1. \(5\) điểm: \(S=N\), \(170\le N\le1\,000\), \(K=3\).
2. \(15\) điểm: \(S=N\), \(N\ge170\).
3. \(10\) điểm: \(S\ge170\) và \(x_{i+1}-x_i\le A/K\) với mọi \(1\le i\le N-1\).
4. \(15\) điểm: \(S\ge170\) và \(x_{i+1}-x_i\le A\) với mọi \(1\le i\le N-1\).
5. \(15\) điểm: \(S\ge170\).
6. \(20\) điểm: \(S\ge40\) và \(x_{i+1}-x_i\le A\) với mọi \(1\le i\le N-1\).
7. \(20\) điểm: \(S\ge40\).

Ví dụ giao tiếp

Xét một bộ dữ liệu có \(N=15\), \(K=3\), \(A=42\) và \(S=8\). Ban đầu, trình chấm gọi solve(15, 3, 42, 8). Sau đây là hai tình huống giao tiếp có thể xảy ra giữa chương trình và trình chấm. Trong các bản ghi, -> chỉ giá trị trả về của hàm; đó không phải là dữ liệu mà bài nộp cần in.

Tình huống thứ nhất:

skim(1) -> 1337
impossible()

Quyển sách đầu tiên, tức quyển dễ nhất, có độ khó \(1337\). Nhờ trực giác kỳ diệu, bạn quyết định rằng không có cách chọn hợp lệ. Kết luận đó đúng và được chấp nhận.

Tình huống thứ hai:

skim(1) -> 7
skim(15) -> 21
answer({11, 15, 7})

Quyển đầu tiên có độ khó \(7\) và quyển cuối cùng có độ khó \(21\). Vì dãy độ khó tăng nghiêm ngặt, nó chứa mọi số nguyên từ \(7\) đến \(21\). Mọi tập giá trị hợp lệ trong dãy có tổng từ \(42\) đến \(84\) đều được chấp nhận. Bạn trả lời bằng các chỉ số sách \(11,15,7\), tương ứng với độ khó \(17,21,13\). Cách chọn này đúng và được chấp nhận.

Trình chấm mẫu

Các thông báo kết thúc của trình chấm mẫu có ý nghĩa như sau:

• Invalid input.: dữ liệu được đưa vào trình chấm qua đầu vào chuẩn không đúng định dạng đã mô tả.
• Invalid skim.: skim được gọi với tham số không hợp lệ.
• Out of books to skim.: skim được gọi quá \(S\) lần.
• Invalid answer.: answer được gọi với tham số không hợp lệ.
• Wrong answer.: answer được gọi với một tập sách không thỏa yêu cầu.
• No answer.: solve kết thúc mà không gọi answer hay impossible.
• Impossible (not checked): s book(s) skimmed.: không xảy ra trường hợp lỗi nào ở trên, skim được gọi \(s\) lần và impossible đã được gọi. Trình chấm mẫu không kiểm tra kết luận không tồn tại cách chọn có đúng hay không.
• Correct: s book(s) skimmed.: không xảy ra trường hợp nào ở trên và skim được gọi \(s\) lần.

Trình chấm dùng để đánh giá bài nộp chính thức chỉ đưa ra Not correct khi có lỗi hoặc Correct khi đúng. Cả trình chấm mẫu và trình chấm chính thức đều tự động kết thúc chương trình khi xảy ra một lỗi đã nêu hoặc khi chương trình gọi answer hay impossible.

Giới hạn

Thời gian: \(1\) giây. Bộ nhớ: \(512\) MiB.