不朽的荣耀属于那些在 BOI 中获得奖牌的人。既然你渴望成为其中一员，这就是你的必经之路*：训练，训练，再训练！

作为训练计划的第一步，你决定购买一些计算机科学书籍。幸运的是，当地书店有一个特别优惠，当你恰好购买 $K$ 本书时，可以享受巨额折扣。

现在，你需要从书店提供的 $N$ 本计算机科学书籍（编号为 $1$ 到 $N$）中选择 $K$ 本购买。你选择的关键因素是难度：每本书 $i$ 都有一个独立的（且完全客观的）难度 $x_i$，而一组书的总难度是它们各自难度之和。你不希望所选书籍太简单（这样你就学不到足够的知识来赢得那枚宝贵的奖牌），也不希望太难（这样在比赛开始前你就无法理解它们）。准确地说，你希望所选书籍的总难度至少为 $A$，但不超过 $2A$。

判断一本书的实际难度需要你浏览它，但如果你在不购买的情况下阅读了太多书籍，店主会不高兴。她允许你最多浏览 $S$ 本书。幸运的是，她还告诉你，这些书是按难度递增排序的。

编写一个程序，协助你决定浏览哪些书籍，并最终告诉你应该购买哪些书籍。

交互

这是一个交互式任务。你必须实现函数 void solve(int N, int K, long long A, int S)，其中 $N, K, A$ 和 $S$ 如上所述。各个书籍的难度 $x_1 < x_2 < \dots < x_N$ 最初对你的程序是隐藏的。对于每个测试用例，该函数会被调用且仅被调用一次。在函数中，你可以使用评测机提供的以下其他函数：

• long long skim(int i)：浏览第 $i$ 本书并返回其难度 $x_i$ ($1 \le i \le N$)。
• void answer(vector<int> v)：购买你选择的书籍。此函数必须使用 $v = \{i_1, \dots, i_K\}$ ($1 \le i_1, \dots, i_K \le N$) 调用，其中 $i_j$ 是两两不同的，且满足 $A \le x_{i_1} + \dots + x_{i_K} \le 2A$。
• void impossible()：声明无法购买到一组满足所需难度的 $K$ 本书。

如果存在一组满足所需难度的 $K$ 本书，你必须调用 answer 恰好一次。否则，你必须调用 impossible 恰好一次。在调用这两个函数之一后，你的程序将自动终止。

如果你的任何函数调用不符合上述格式，或者你调用 skim 的次数超过了 $S$ 次，你的程序将立即终止，并被判定为该测试用例的“不正确”（Not correct）。你不得向标准输出写入任何内容，否则你可能会收到“安全违规”（Security violation!）的判决。

如果你使用 C++，必须在源代码中包含文件 books.h。为了在本地测试你的程序，你可以将你的程序与 sample_grader.cpp 链接，该文件可以在 CMS 中该任务的附件中找到（下文有关于样例评测机的描述）。附件中还包含一个带有额外说明的示例实现 books_sample.cpp。

如果你使用 Python，可以在附件中找到示例实现 books_sample.py，其中也描述了 Python 提交的接口。

* “真的吗？”你脑海中有一个微小的声音说道……

数据范围

我们始终有 $K \le N$，$3 \le N$，$S \le 10^5$，$1 \le A, x_i \le 10^{17}$，且 $3 \le K \le 10$。

• 子任务 1（5 分）：$S = N$，$170 \le N \le 1000$，$K = 3$
• 子任务 2（15 分）：$S = N$，$N \ge 170$
• 子任务 3（10 分）：$S \ge 170$，$x_{i+1} - x_i \le A/K$ 对于所有 $1 \le i \le N - 1$
• 子任务 4（15 分）：$S \ge 170$，$x_{i+1} - x_i \le A$ 对于所有 $1 \le i \le N - 1$
• 子任务 5（15 分）：$S \ge 170$
• 子任务 6（20 分）：$S \ge 40$，$x_{i+1} - x_i \le A$ 对于所有 $1 \le i \le N - 1$
• 子任务 7（20 分）：$S \ge 40$

样例

考虑一个 $N = 15, K = 3, A = 42, S = 8$ 的测试用例。开始时，评测机调用你的函数 solve(15, 3, 42, 8)。然后，你的程序与评测机之间可能的交互如下：

样例 1

样例 2

说明

样例评测机期望在标准输入中输入两行。第一行应包含四个整数 $N, K, A$ 和 $S$。第二行应包含一个由 $N$ 个整数组成的列表，即严格递增的难度序列 $x_1, x_2, \dots, x_N$。然后，评测机将向标准输出写入你的程序所调用的所有评测机函数的协议。最后，评测机会向标准输出写入以下消息之一：

• Invalid input.：输入到评测机的标准输入不符合上述格式。
• Invalid skim.：函数 skim 被以无效参数调用。
• Out of books to skim.：函数 skim 被调用的次数超过了 $S$ 次。
• Invalid answer.：函数 answer 被以无效参数调用。
• Wrong answer.：函数 answer 被以错误的书籍选择调用。
• No answer.：函数 solve 在没有调用 answer 或 impossible 的情况下终止。
• Impossible (not checked): s book(s) skimmed.：上述情况均未发生，函数 skim 被调用了 $s$ 次，且函数 impossible 被调用。未检查这是否是正确的答案。
• Correct: s book(s) skimmed.：上述情况均未发生，且函数 skim 被调用了 $s$ 次。

相比之下，用于评估你提交代码的评测机只会输出 Not correct（针对上述任何错误）或 Correct。无论是样例评测机还是用于评估的评测机，只要发生上述任何错误，或者你的程序调用了 answer 或 impossible，都会自动终止你的程序。