U120842.The Strict Teacher (Hard Version)

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(1\le n\le2 * 10^5,1\le m,q\le2 * 10^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 \le t \le 10^4$。
• $1 \le n, m \le 2 \cdot 10^5$。
• $1 \le a_i, b_j \le 10^9$。