Bajtazar 国王决定建造一座新宫殿。他为此举办了一场宫殿最佳建筑设计竞赛。为了激励建筑师们抓紧工作，他宣布将按照项目提交的先后顺序进行评审。

这项任务享有极高的声望，因此来自世界各地的建筑师纷纷向皇家办公室提交方案。项目数量非常多，而 Bajtazar 没有时间一一审阅。因此，他放弃了亲自处理这项工作，并要求他的大臣根据以下原则对收到的项目进行初步筛选：

• 大臣必须选择 $k$ 个项目，并立即拒绝其余项目——Bajtazar 知道他最多只能审阅 $k$ 个项目；
• 项目必须按照提交的先后顺序呈现给 Bajtazar——这也是 Bajtazar 按照他所宣布的顺序进行审阅的顺序；
• 在所有满足上述条件的 $k$ 个项目序列中，大臣必须选择“最佳”序列，定义如下： 如果对于某个 $l \ge 1$，两个序列的前 $l-1$ 个项目相同，且序列 $p$ 的第 $l$ 个项目优于序列 $r$ 的第 $l$ 个项目（即对于 $i < l$ 有 $p_i = r_i$，且 $p_l > r_l$），则称项目序列 $(p_1, p_2, \dots, p_k)$ 优于序列 $(r_1, r_2, \dots, r_k)$。

项目一直在源源不断地送达，目前尚不清楚 Bajtazar 何时会下令停止接收。大臣不想把选择 $k$ 个项目的决定留到最后一刻，但他非常担心犯错并招致国王的愤怒。因此，他请求你的帮助。

交互

你的程序不应从标准输入读取任何内容，也不应向标准输出写入任何内容。相反，它将与一个评测库进行链接。在程序开头，请包含以下指令：

#include "arc.h"

该库提供以下函数：

• int inicjuj() – 返回一个整数 $k$ ($1 \le k \le 1\,000\,000$)，表示结果序列应包含的项目数量。该函数应在程序开始时调用且仅调用一次。
• int wczytaj() – 第 $i$ 次调用返回一个整数 $p_i$ ($1 \le p_i \le 1\,000\,000\,000$)，表示第 $i$ 个项目的质量（数字越大，项目越好），或者返回 $0$，表示没有更多项目了。在读取数据之前，项目总数是未知的，但你可以假设总项目数至少为 $k$，且最多为 $15\,000\,000$。此函数应在项目用尽前一直调用，且不得多调用一次。
• void wypisz(int jakoscProjektu) – 使用此函数输出大臣将呈现给国王的后续项目的质量。该函数应被调用恰好 $k$ 次；在第 $i$ 次调用时，应提供序列中第 $i$ 个项目的质量。第 $k$ 次调用此函数将结束你的程序。

样例

实现细节

在“文件”部分，你可以找到一个示例库和解决方案，说明了它们的使用方法。示例库从标准输入读取测试场景，格式如下：输入的第一行包含一个正整数 $k$。接下来的每一行包含一个正整数；第 $(i+1)$ 行包含数字 $p_i$，表示第 $i$ 个提交项目的质量。输入的最后一行包含数字 $0$，表示项目列表结束。示例库将程序报告的项目质量输出到标准输出，共 $k$ 行。

要测试你的程序，请使用类似于以下的命令进行编译（假设你的解决方案位于 arc.cpp 文件中）：

g++ -O2 -std=c++11 arc.cpp arczaw.c -o arc

这将创建一个名为 arc 的可执行文件。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。 请记住，$n$ 表示项目总数。

“评估”测试： 1. $k = 1, n = 6$ 2. $k = 2, n = 5$ 3. $k = 3, n = 8$ 4. $k = 5, n = 10$ 5. $k = 100\,000, n = 100\,000$