配点: 100 点
問題文
JOI市有 1 本非常长的道路。这条道路可以看作数轴,每个地点用 1 个实数的坐标表示。
此外,JOI市沿这条道路有 N 个钟,按坐标从小到大排列,编号为 1 从 N 。钟 i (1 ≦ i ≦ N) 在坐标 A_i 。
在 JOI 市,1 年底同时敲响这些钟是一大活动。
无论哪个钟,敲响时在该钟同一地点能听到强度为 K 的声音,但随着距离 1 的增加,能听到的声音强度会 1 变小,当距离达到 K 时,强度为 0 。也就是说,当敲响钟 i 时,坐标 x 能听到的钟 i 的声音强度为 \max\{K - |x - A_i|, 0\} 。 其中,|t| 是 小于或等于 t 表示绝对值。
当所有的钟都被敲响时,坐标 x 能听到的钟声强度是坐标 x 所能听到的每个钟声强度的最大值。
JOI市沿着这条道路有 M 个房子,从旧到新的顺序编号为 1 从 M 。房子 j (1 ≦ j ≦ M) 在坐标 B_j 。
作为打飞机市的市长的你,希望在所有钟都敲响时,知道每个房子能听到的钟声强度。
给定JOI市的钟和房屋的信息时,当所有钟都敲响时,求出在坐标 B_1, B_2, …, B_M 的钟声强度的程序。
制約
- 1 \leqq N \leqq 250\,000.
- 1 \leqq M \leqq 250\,000.
- 1 \leqq K \leqq 10^9.
- 0 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- A_i \lt A_{i+1} (1 \leqq i \leqq N - 1).
- 0 \leqq B_j \leqq 10^9 (1 \leqq j \leqq M).
- B_j ≠ B_k (1 \leqq j < k \leqq M).
- 所有输入值都是整数。
小課題
- (20 点) N = 1,M \leqq 1\,000.
- (20 点) N \leqq 1\,000,M \leqq 1\,000.
- (60 点)没有额外的限制。
入力
输入按以下格式给出。
N M K A_1 A_2 \cdots A_N B_1 B_2 \cdots B_M
出力
M 按行输出。j 行目 (1 \leqq j \leqq M) 中,输出在所有钟都敲响时,坐标 B_j 的钟声强度。
入力例 1
1 5 10 20 20 15 28 10 32
出力例 1
10 5 2 0 0
在这个输入实例中,坐标 20 上有钟。 1 是
- 鐘 1 时,坐标 20 能听到的钟 1 的声音强度为 \max\{10 - |20 - 20|, 0\} = 10 。因此,在坐标1 在线 写在方格 10 。
- 鐘 1 时,坐标 15 能听到的钟 1 的声音强度为 \max\{10 - |15 - 20|, 0\} = 5 。因此,在坐标2 在线 写在方格 5 。
- 鐘 1 时,坐标 28 能听到的钟 1 的声音强度为 \max\{10 - |28 - 20|, 0\} = 2 。因此,在坐标3 在线 写在方格 2 。
- 鐘 1 时,坐标 10 能听到的钟 1 的声音强度为 \max\{10 - |10 - 20|, 0\} = 0 。因此,在坐标4 在线 写在方格 0 。
- 鐘 1 时,坐标 32 能听到的钟 1 的声音强度为 \max\{10 - |32 - 20|, 0\} = 0 。因此,在坐标5 在线 写在方格 0 。
此输入示例满足所有子任务约束。
入力例 2
3 4 100 116 194 258 57 155 222 360
出力例 2
41 61 72 0
- 鐘 1,2,3 时,坐标 57 能听到的声音强度分别为 41,0,0 。因此,当所有钟都被敲响时,在坐标 57 处听到的声音强度是这些最大值 41 。因此,1 在线 写在方格 41 。
- 鐘 1,2,3 时,坐标 155 能听到的声音强度分别为 61,61,0 。因此,当所有钟都被敲响时,在坐标 155 处听到的声音强度是这些最大值 61 。因此,2 在线 写在方格 61 。
- 鐘 1,2,3 时,坐标 222 能听到的声音强度分别为 0,72,64 。因此,当所有钟都被敲响时,在坐标 222 处听到的声音强度是这些最大值 72 。因此,3 在线 写在方格 72 。
- 鐘 1,2,3 时,坐标 360 能听到的声音强度分别为 0,0,0 。因此,当所有钟都被敲响时,在坐标 360 处听到的声音强度是这些最大值 0 。因此,4 在线 写在方格 0 。
此输入示例是一个小作业。 2, 3 满足约束。 在
入力例 3
10 10 10000 589 2398 6567 28817 29177 31636 45468 66751 82282 97509 2196 54498 80474 61644 18007 38759 85590 72172 79533 69959
出力例 3
9798 970 8192 4893 0 3291 6692 4579 7251 6792
此输入示例是一个小作业。 2, 3 满足约束。 在