题目描述

译自 ROI 2013 Day2 T2. Морской бой

在乌拉尔锦标赛框架内，计划举办一场「1D海战」策略游戏锦标赛。

游戏在一个大小为 $1 \times N$ 的矩形网格上进行。网格上放置 $T$ 艘船，每艘船为大小 $1 \times K$ 的矩形。如果不同船之间没有共享格子，并且至少由一个空格分隔，我们称船的放置是合法的。游戏程序会在网格的格子上进行射击，服务器会告知射击是未命中还是命中船只。

在游戏过程中，某些格子被确认为在任何合法的船只放置方式下都必然属于某艘船，我们称这些格子为必然被占用的格子。

游戏在首次命中船只后结束。服务器试图让游戏尽可能长时间持续。为此，服务器不在游戏开始时固定船只的放置方式，而是考虑所有可能的合法放置方式，仅当射击的格子是必然被占用的格子时才报告命中。

你需要编写一个程序，扮演服务器的角色。首先加载游戏参数，然后与游戏程序交互，在每次射击后报告未命中或命中的信息，并提供必然被占用格子的数量。

交互方式

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

游戏程序由评测程序扮演，参赛者的程序扮演服务器角色。

程序从标准输入流读取的第一行包含游戏参数——三个整数：$N$（网格大小）、$T$（船只数量）和 $K$（每艘船的长度） $(1 \leq N \leq 100000, 1 \leq T, 1 \leq K)$。保证在长度为 $N$ 的网格上可以按照规则放置 $T$ 艘长度为 $K$ 的船只。

读取参数后，程序应计算并输出到标准输出流的必然被占用格子数量。

随后开始游戏，程序需按照以下步骤与游戏程序交互：

1. 从标准输入流读取一个整数 $q$ $(1 \leq q \leq N)$，表示游戏程序射击的格子编号。游戏程序不会对同一格子进行两次射击。
2. 如果格子 $q$ 是必然被占用的，输出数字 $1$ 到标准输出流，并结束程序。
3. 如果格子 $q$ 不是必然被占用的，输出两个以空格分隔的整数到标准输出流：$0$ 和此次射击后必然被占用的格子数量。

随后返回步骤 1，继续与游戏程序交互。

8 2 3
4
1

4
0 5
1

游戏在一个包含 $8$ 个格子的网格上进行，放置 $2$ 艘船，每艘船占用 $3$ 个格子。所有合法的船只放置方式如下图所示。标记为 # 的格子为必然被占用的格子，共有 $4$ 个。

第一次射击在编号为 $4$ 的格子上，这次射击被认为是未命中，剩余的合法放置方式如下图所示。此时有 $5$ 个格子是必然被占用的。

第二次射击在编号为 $1$ 的格子上，该格子不可能是必然被占用的，因此游戏结束。

数据范围与提示

详细子任务附加限制及分值如下表所示：