题目背景

本题为交互题。

感谢交互库与 checker 的提供者 Hi_chocolate 为本题做出的巨大贡献。

特别提示

在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：

1. 提交时请在程序里加入以下函数声明语句：

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

你实现的 solve 函数应为：

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

2. 程序开头不用，也不应该包含 books.h 头文件。
3. 仅支持 C++（含 C++，C++11，C++14，C++17）提交。

题目描述

您致力于 AK BalticOI，而 AK BalticOI 的方式就是学习。您走进了一家书店，架子上有 $N$ 本书，编号为 $1$ 到 $N$，第 $i$ 本的难度为 $x_i$。您要从这 $N$ 本书中挑选出 $K$ 本书用来学习，您不希望学到太简单或太难的东西，所以您想要保证这 $K$ 本书的难度之和位于 $[A,2A]$ 的区间内。

可惜的是，您并不知道 $x_i$ 的具体数值，所以您要浏览这些书籍以得知他们的难度。书店老板有洁癖，他不希望您浏览太多的书籍，所以他规定您最多只能浏览 $S$ 本书，然后确定这些书的难度。幸运的是，您被告知这 $N$ 本书按照编号的增加，难度呈单调递增。

请编写一个程序，通过浏览书籍，购买您需要的书籍，或者指出无解。

交互格式

本题为交互题，您需要编写 void solve (int N, int K, long long A, int S) 函数，$N,K,A,S$ 在上面已经定义，并且保证 $x_1<x_2<\cdots<x_n$，该函数只被调用一次。

您还可以调用如下的函数：

• long long skim (int i) 浏览第 $i$ 本书以获取他的难度 $x_i$。
• void answer (vector<int> v) 买您所需要的书。其中 $v=\{i_1,i_2,\cdots,i_K\}$，并且需要满足：

$$A \le \sum\limits_{j=1}^K i_j \le 2A$$

• void impossible () 指出不可能按照要求买下 $K$ 本书。

如果存在满足要求的 $K$ 本书，您必须准确地调用 answer 函数一次；否则您需要准确地调用 impossible 函数一次。调用过后，程序会自动停止。

如果您的函数调用不符合上面的格式，或者调用了超过 $S$ 次 skim 函数，程序会自动停止，这个测试点会判为 Not correct；你不能在标准输出中输出任何东西，否则会被判为 Security violation。

如果您使用 C++ 编码，请调用 books.h 头文件，如果您想检验您的程序的正确性，可以在下方附件中下载 sample_grader.cpp 与 books_sample.cpp，分别为您提供检验正确性和示例说明的作用。

如果您使用 Python 编码，可以在下方附件中下载 books_sample.py 检验。

交互库希望标准输入里有两行：

• 第一行四个整数，$N,K,A,S$。
• 第二行 $N$ 个整数，$x_1,x_2,\cdots,x_N$。

随后，交互库会调用您的程序，最后，交互库会在标准输出中返回信息：

信息	意义
Invalid input.	标准输入的格式错误
Invalid skim.	skim 函数调用无效
Out of books to skim.	skim 函数调用超过 $S$ 次
Invalid answer.	answer 函数调用无效
Wrong answer.	answer 函数调用的 $v$ 不满足要求
No answer.	solve 函数没有调用 answer 函数和 impossible 函数中的任意一个
Impossible (not checked): s book(s) skimmed.	上述事件都没有发生，调用了 $S$ 次 skim 函数，并在有答案的时候调用了 impossible 函数
Correct: s book(s) skimmed.	上述事件都没有发生，调用了 $S$ 次 skim 函数

针对上面若干个错误的情况，交互库仅会返回 Not correct，或者正确的时候返回 Correct。每当出现上面的若干个错误，或者您的程序调用了 answer 或 impossible 函数时，程序会被自动停止。

输入格式

见「交互格式」。

输出格式

见「交互格式」。

15 3 42 8

提示

样例 1 解释

$N=15$，$K=3$，$A=42$，$S=8$，下面是可能的两种会被判为通过的调用结果：

示例 1：

你的程序	返回值
skim(1)	$1337$
impossible	-

示例 2：

你的程序	返回值
skim(1)	$7$
skim(15)	$21$
answer({11,15,7})	-

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$S=N$，$170 \le N \le 1000$，$K=3$。
• Subtask 2（15 pts）：$S=N$，$N \ge 170$。
• Subtask 3（10 pts）：$S \ge 170$，$x_{i+1}-x_i \le \frac A K$。
• Subtask 4（15 pts）：$S \ge 170$，$x_{i+1}-x_i \le A$。
• Subtask 5（15 pts）：$S \ge 170$。
• Subtask 6（20 pts）：$S \ge 40$，$x_{i+1}-x_i \le A$。
• Subtask 7（20 pts）：$S \ge 40$。

对于 $100\%$ 的数据，$K \le N$，$3 \le N,S \le 10^5$，$1 \le A,x_i \le 10^{17}$，$3 \le K \le 10$。

说明

翻译自 BalticOI 2021 Day1 A A Difficulty Choice。