CF2005B2 The Strict Teacher (Hard Version)

**这是本题的困难版，它和本题的简单版的唯一差距是 $m$ 和 $q$ 的数据范围**。在此版本中，$m,q\le10^5$。你在解决两个版本之后才可以去提交 hack 数据。 Narek 和 Tsovak 正在热火朝天地准备这场比赛，所以他们没时间去做作业了，因此，他们决定去偷 David 的作业。 严厉的老师发现 David 的作业没了非常生气，打算狠狠地惩罚他，于是她雇佣了别的老师帮她一起抓捕 David。 现在有 $m$ 个老师正在一起追 David。幸运的是，教室非常的大，所以 David 有充足的躲藏空间。 教室可以被表示为一条一维直线，上面有 $n$ 个单元格编号从 $1$ 到 $n$，**包含边界。** 最初，David 和这 $m$ 个老师**在不同的单元格中**。然后他们将会进行若干次行动。每次行动中： - 首先，David 可以移动到一个**相邻的**单元格中，**也可以不动。** - 然后，每位老师也进行这样的一次移动。 行动将一直持续知道 David 被抓住，即有任何一个老师和 David 位于同一个单元格中。**所有人都看得见其它人的行动。** 你的任务是计算**在所有人按照最优方案行动的前提下，多少次行动后 David 会被抓住。** > 按照最优方案行动，是指： > - David 采取一种方案，使得老师抓住他所需的行动次数最大。 > - 老师之间相互配合并采用一种方案，使得他们能够用最少的行动次数抓住 David。 Narek 和 Tsovak 认为这个任务太简单了，于是他们决定给你 $q$ 次询问。

**每个测试点有多组数据。** 第一行有一个正整数 $t(1\le t\le10^5)$，表示数据的组数。 每组数据的第一行有三个正整数 $n,m,q(3\le n\le10^9,1\le m,q\le10^5)$，分别表示单元格个数，老师个数，和询问次数。 每组数据的第二行有 $m$ 个**不同的**正整数 $b_1,b_2,\dots,b_m(1\le b_i\le n)$，代表每个老师初始的位置。 每组数据的第三行有 $q$ 个正整数 $a_1,a_2,\dots,a_q(1\le a_i\le n)$，代表每次询问中 David 的初始位置。 保证 $\forall i\in[1,m],j\in[1,q],b_i\ne a_j$。 保证 $\sum m,\sum q\le2\cdot10^5$。

对于每组数据，输出 $q$ 行，第 $i$ 行是这组数据中的第 $i$ 次询问的答案。 ### 样例解释翻译 在样例 $1$ 的唯一一次询问中，David 可以跑到 $1$ 号单元格。老师需要 $5$ 步来从 $6$ 号单元格跑到 $1$ 号单元格，所以答案为 $5$。 在样例 $2$ 的第二次讯问中，David 可以一直呆在 $3$ 号单元格。初始位于 $4$ 号单元格的老师一步就可以走到 $3$ 号单元格。因此答案为 $1$。

In the only query of the first example, the student can run to cell $ 1 $ . It will take the teacher five moves to reach from cell $ 6 $ to cell $ 1 $ , so the answer is $ 5 $ . In the second query of the second example, the student can just stay at cell $ 3 $ . The teacher, initially located in cell $ 4 $ , can reach cell $ 3 $ in one move. Therefore, the answer is $ 1 $ .