题目背景

交互库来自 LibreOJ。

题目描述

作为乌拉尔锦标赛的一部分，计划举办“一维海战”游戏策略比赛。

游戏在战场上进行，战场是一个 $1 \times N$ 个单元格的矩形。战场上放置了 $T$ 艘战舰，每艘战舰是一个 $1 \times K$ 个单元格的矩形。如果不同的战舰没有共用单元格且至少被一个空单元格分隔，则战场上的战舰布置是 允许的。游戏程序向战场上的单元格发射炮弹，服务器报告该射击是未命中还是命中战舰。

在游戏过程中，某些单元格被确认为：在任何允许的战舰布置下，它们都属于某艘战舰。我们称这些单元格为 明确被占 单元格。

游戏在首次命中战舰后结束。服务器试图使游戏尽可能长时间地进行。为此，它不在游戏开始时固定战舰布置，而是考虑所有可能的允许布置，并且仅当射击的单元格是明确被占单元格时才报告命中。

需要编写一个程序，扮演该游戏的服务器角色。服务器首先加载游戏参数，然后与游戏程序交互，在每次射击后报告未命中或命中的信息，以及明确被占单元格的数量。

交互格式

本题是交互题。 每次输出后需要刷新输出缓冲区。

游戏程序由评测系统程序扮演。解题程序扮演服务器角色。

解题程序的标准输入第一行包含游戏参数——三个数字：$N$ 表示战场大小，$T$ 表示战舰数量，$K$ 表示每艘战舰的长度（$1 \le N \le 100,000$，$1 \le T$，$1 \le K$）。保证在长度为 $N$ 的战场上可以按照所述规则放置 $T$ 艘长度为 $K$ 的战舰。

读取游戏参数后，解题程序必须确定并输出到标准输出流中明确被占单元格的数量。

然后游戏开始。解题程序必须依次从标准输入流读取游戏程序的走步，并按以下方式处理：

1. 从标准输入流读取一个数字 $q$——游戏程序射击的单元格编号（$1 \leqslant q \leqslant N$）。游戏程序永远不会两次射击同一个单元格。
2. 如果单元格 $q$ 是明确被占的，则输出数字 $1$ 到标准输出流并结束工作。
3. 如果单元格 $q$ 不是明确被占的，则输出两个用空格分隔的数字到标准输出流：$0$ 和此次射击后明确被占单元格的数量。

之后，解题程序转到第 1 步，继续与游戏程序交互。

8 2 3
4
1

4
0 5
1

提示

样例解释

游戏在由 $8$ 个单元格组成的战场上展开，战场上放置了 $2$ 艘战舰，每艘由 $3$ 个单元格组成。所有允许的战舰布置如图 1 所示。标记为 # 的单元格是明确被占的。这样的单元格有 $4$ 个。

:::align{center}

图 1. 游戏开始时允许的战舰布置。 :::

第一次射击针对编号为 $4$ 的单元格。这次射击被视为未命中，剩余允许的战舰布置如图 2 所示。现在有 $5$ 个单元格是明确被占的。

:::align{center}

图 2. 第一次射击后允许的战舰布置。 :::

第二次射击针对编号为 $1$ 的单元格，该单元格不可能是明确被占的，因此游戏结束。

评分

本题包含三个子任务。每个子任务的评分使用独立的测试组。仅当通过该组所有测试时，子任务的得分才会被计入。

子任务 1

$N \le 15$。该子任务分值为 $30$ 分。

子任务 2

$N \le 3000$。该子任务分值为 $30$ 分。

子任务 3

$N \le 100,000$。该子任务分值为 $40$ 分。