Bessie提前知道，列车有$N$节车厢（$1 \leq N \leq 10^6$），方便起见编号为$0 \dots N-1$。车厢$i$有一个编号$c_i$写在上面（$0 \le c_i \le 10^9$）。所有的数字在早晨和下午都能被看见，所以对于每节车厢Bessie有两次机会观察它的编号。也就是说，当列车早晨经过的时候，Bessie能够观察$c_0$，然后是$c_1$，直到$c_{N-1}$。当列车下午驶回的时候，她又一次能够观察$c_0$，然后是$c_1$，直到$c_{N-1}$。

Bessie挑选了一个整数$K$（$1 \leq K \leq N$），她想要求出每个连续的$K$节车厢中最小的编号。她有一本能够帮助执行计算的笔记本，但是它相当小，并且Bessie的手写（蹄写？）字相当大。比方说，可能没有足够的空间记下所有$N+1-K$个最小值。由于某些神秘的原因，Bessie满足于当她算出最小数的时候向天哞出这些数，所以这个问题至少还不成问题。

列车马上就要来了！帮助Bessie在列车经过两次之后求出这$N + 1 - K$个最小数，确保她有效地利用她有限的笔记本空间。她的笔记本被分为$5500$个部分，方便起见编号为$0 \dots 5499$，每个部分的空间恰好能够记录一个在$-2^{31}$ and $2^{31}-1$之间的整数。最初的时候，每个部分都记录着整数$0$。

这是一道交互式题目，你不需要使用标准（或文件）输入输出。具体地说，你需要实现下面的函数，这个函数用来帮助Bessie有效管理她有限的笔记本空间：

void helpBessie(int ID);

每当一节列车车厢经过的时候，无论是在早晨和下午，你的函数都会被调用，函数的输入是这节车厢的编号。

你的$\texttt{helpBessie}$函数的实现可以调用下面这些函数：

• int get(int index): 获取记录在Bessie的笔记本上的给定的索引处的整数值（index）。
• void set(int index, int value): 设置给定的索引（index）处的值为给定的整数值（value）。
• void shoutMinimum(int output): 通知Bessie向天哞一个指定的数。
• int getTrainLength(): 返回列车的车厢数$N$。
• int getWindowLength(): 返回窗口的长度$K$。
• int getCurrentCarIndex(): 返回当前正在通过的车厢序号。
• int getCurrentPassIndex(): 如果Bessie正在观察早晨的列车返回$0$，下午的列车返回$1$。

为了帮助你开始编码，我们为你提供了初始的C/C++和Java模板。遗憾地，这道题目不支持Python和Pascal的提交。

各个窗口的最小数必须按顺序输出（所以车厢$0, 1, \dots, K-1$之中的最小值必须在车厢$1, 2, \dots, K$之中的最小值之前输出，等等），但是除了这个顺序的限制之外，你的函数可以在任何一次函数调用中任意多次地输出一些最小值。比如，你的函数可能在某几次调用中不产生任何输出，而在某几次调用中产生多个输出。

Bessie拥有惊人的短时记忆能力，因此在$\texttt{helpBessie}$函数中没有任何的内存使用限制，除了要满足常规的256MB限制。然而，在车厢与车厢之间，Bessie不能够“记住”任何不在笔记本中出现过的内容。所以在两次函数调用之间，你的程序除了通过$\texttt{get}$和$\texttt{set}$函数调用之外不能保存任何的状态。

这意味着：

不允许定义任何非常量的全局或静态变量。任何如此做的提交会被取消成绩。教练会人工检查所有的提交以验证是否符合题目要求。由于这个问题无需文件输入输出，所以也不允许在代码中使用任何的文件输入输出。

对于每个测试点，你的程序进行的$\texttt{set}$调用和$\texttt{get}$调用的总次数被限制为$25 \cdot 10^6$次。

输入样例：

10 3
5 7 9 2 0 1 7 4 3 6

输出样例：

5
2
0
0
0
1
3
3

供题：Dhruv Rohatgi