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$。