分数: 400 点
问题陈述
沿着一条东西方向的道路,有 A 神社和 B 寺庙。 的 i从西数第一个神社位于距离 s_i 距离道路西端米,并且 i从西数第一个寺庙位于距离 t_i 距离道路西端米。
回答以下问题 Q 查询:
- 查询 i (1 \leq i \leq Q):如果我们从距离为 x_i 距离道路西端米,沿道路自由行驶,参观一神社一寺庙最少需要行驶多少距离? (允许通过超过规定数量的神社和寺庙。)
约束
- 1 \leq A, B \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq s_1 < s_2 < ... < s_A \leq 10^{10}
- 1 \leq t_1 < t_2 < ... < t_B \leq 10^{10}
- 1 \leq x_i \leq 10^{10}
- s_1, ..., s_A, t_1, ..., t_B, x_1, ..., x_Q 都是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
A B Q s_1 : s_A t_1 : t_B x_1 : x_Q
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
2 3 4 100 600 400 900 1000 150 2000 899 799
示例输出 1
350 1400 301 399
有两个神社和三个寺庙。这些神社的距离为 100, 600 距离道路西端 米,寺庙位于 400, 900, 1000 距离道路西端米。
- 查询 1:如果我们从距离为 150 距离道路西端米,最佳移动方式是先步行 50 向西米去参拜神社,然后步行 300 米东参观寺庙。
- 查询 2:如果我们从距离为 2000 距离道路西端米,最佳移动方式是先步行 1000 向西1米参观一座寺庙,然后步行 400 米西去参拜神社。途中我们会经过另一座寺庙,不过还好。
- 查询 3:如果我们从距离为 899 距离道路西端米,最佳移动方式是先步行 1 向东一米参观寺庙,然后步行 300 米西去参拜神社。
- 查询 4:如果我们从距离为 799 距离道路西端米,最佳移动方式是先步行 199 向西米去参拜神社,然后步行 200 米西去参观一座寺庙。
示例输入 2
1 1 3 1 10000000000 2 9999999999 5000000000
示例输出 2
10000000000 10000000000 14999999998
路很长,我们可能需要走一段不适合的距离 32位整数。