P12914 [POI 2020/2021 R2] 沙滩游客 / Plażowicze

翻译来自于 [LibreOJ](https://loj.ac/p/4832)。

**题目译自 [XXVIII Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi28-2/dashboard/) [Plażowicze](https://szkopul.edu.pl/problemset/problem/mSKiDD4jrokeNO__pazg6BaF/statement/)** 每年，字节海边的沙滩都会吸引来自整个字节王国的游客。现在，沙滩上有 $n$ 个常客在休息，他们都铺着毯子紧靠着海岸线（每个人都想离水越近越好）。因此，每块毯子的位置可以用距离沙滩起点的距离（单位：米）来描述。海岸线总长 $X$ 米，所以毯子的位置是 $0$ 到 $X$ 之间的整数。为了简化，我们假设毯子的尺寸小到可以忽略不计。沙滩的起点 $0$ 和终点 $X$ 处都有毯子。这些常客一整天都待在固定的位置晒太阳。 字节王国的人喜欢在休息时享受宁静。每当一个新游客来到沙滩，他都会选择一个靠近海岸线的地方铺毯子，同时尽量远离其他人的毯子（也就是最大化与最近毯子的距离）。如果有多个这样的位置，他会挑离沙滩起点最近的那个（因为那里有附近最好的冰激凌摊）。新游客的毯子位置不一定是整数。 现在，一辆载满游客的大巴刚到沙滩，其中包括 Bajtazar。他喜欢坐在大巴最后一排，所以总是最后一个下车。请你告诉他，根据大巴里总共有 $k$ 个游客，他应该把毯子铺在哪里。

输入的第一行包含三个整数 $n, X, z$ $(2 \leq n \leq 10^{6}, 1 \leq X \leq 10^{9}, 1 \leq z \leq 10^{5})$，分别表示常客数量、沙滩长度和询问次数。 第二行包含 $n$ 个整数 $x_{1}, x_{2}, \ldots, x_{n}$ $(0 = x_{1} < x_{2} < \ldots < x_{n} = X)$，表示常客毯子的位置。 接下来的 $z$ 行是询问，每行包含一个整数 $k_{i}$ $(1 \leq k_{i} \leq 10^{9})$，表示第 $i$ 次询问中大巴里的游客总数。

输出应包含正好 $z$ 行，依次回答输入中的每个询问。第 $i$ 行应输出一个不可约分数的形式 $p / q$ $(0 \leq p / q \leq X$，且 $p, q$ 为正整数)，表示如果大巴里有 $k_{i}$ 个游客，且他们在字节扎尔之前都铺好毯子，他应该铺毯子的位置。

**样例 1 解释** 如果大巴里有 $k=8$ 个游客，游客按下车顺序铺毯子的位置依次是 $5, 8\frac{1}{2}, 1, 4, 6, 7\frac{3}{4}, 9\frac{1}{4}$ 和 $\frac{1}{2}$（Bajtazar）。注意，第一个、第二个、第五个和第六个位置分别是其他询问的答案。 **附加样例** 1. 该样例满足 $X = 15, n = 3; z = 10, k_i = i$。 2. 该样例满足 $X = 1, n = 2, z = 1, k_1 = 10^9$； 3. 该样例满足 $X = 10^6 - 1, n = 10^6, z = 10^5, k_i = i$； 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $z=1 ; k_{1} \leq 10^{5}$ | $20$ | | $2$ | $n=2$ | $10$ | | $3$ | $n \leq 10^{4} ; z \leq 5$ | $20$ | | $4$ | $n \leq 10^{4}$ | $30$ | | $5$ | $z \leq 10^{3}$ | $10$ | | $6$ | 无附加限制 | $10$ |