奶龙

题目描述

暴暴龙习得了分身术，他想抓住奶龙，奶龙需要躲避暴暴龙的追捕。

奶龙和暴暴龙的位置关系可以抽象为一条数轴上的两个整数点。在 $[1,n]$ 的范围内，分布有 $m$ 个暴暴龙。每个单位时间，暴暴龙会向着奶龙的方向移动一单位长度，或者选择不移动。

奶龙也会以类似的移动方式进行躲避。现在奶龙给出了 $q$ 个位置，请你帮他求一求，对于每一个位置奶龙会被暴暴龙抓住的最短时间。（奶龙与任意一个暴暴龙重合视为被抓住。）

奶龙和暴暴龙都绝顶聪明，因此他们都会采取最优策略。

输入格式

第一行，三个整数，$n, m, q$，分别表示数轴的范围，暴暴龙的分身的数量和询问的数量；

第二行，$m$ 个整数，表示暴暴龙的坐标 $x_1,x_2, \cdots ,x_m$；

接下来 $q$ 行，每行一个整数，表示该次询问奶龙的位置 $q_i$。

输出格式

共 $q$ 行，对于每一个 $q_i$ 输出最短时间。

输入输出样例

输入 #1

10 2 3
3 7
2
6
9

输出 #1

2
2
3

输入 #2

1000 10 7
521 474 324 992 498 572 898 864 456 866
526
326
258
573
431
460
222

输出 #2

25
66
323
146
66
9
323

说明 / 提示

数据范围与约定

测试点	$n\leq$	$m\leq$	$q\leq$	特殊性质
$1\sim2$	$10^{4}$	$100$
$3\sim7$	$10^{6}$	$1000$	$10^{4}$
$8$			$100$	$A$
$9\sim10$	$10^{18}$	$10^{5}$	$10^{5}$	$B$
$11\sim20$		$10^{6}$

特殊性质 $A$：保证每次询问的奶龙的位置的左右两边都是暴暴龙（边界除外）。

特殊性质 $B$：保证所有暴暴龙的分身在一起。形式化地，$\forall i, j \in [1, m], |x_i-x_j|< m$。

对于所有的数据，保证暴暴龙的位置与询问的奶龙的位置不同。

对于所有的数据，保证 $1\leq q_i, x_i \leq n\leq 10^{18}, 1\leq m \leq 10^6, 1 \leq q \leq 10^5$。

本题输入输出量较大，请使用较快的读入读出方式。

如果您使用 cin cout 读入读出，建议在 main() 函数的第一行添加：

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);