https://codeforces.com/problemset/problem/2005/B2

这是本题的困难版本。与简单版本相比，区别仅在于对变量 m 和 q 的限制更大。在你通过两个版本后，才能进行 hack 操作。

Narek 和 Tsovak 正忙于准备比赛，因此没有时间完成作业，打算偷 David 的作业。老师发现 David 没有作业，为了惩罚他，请来其他老师一起捉住 David。现在有 m 位老师一起追赶 David。幸运的是，教室很大，David 有很多地方可以躲。

教室可以看作是一条从 1 到 n 的一维直线。

一开始，所有 m 位老师和 David 都处于不同的位置。之后他们开始行动。每一轮移动中：

David 可以移动到相邻的格子，或者保持不动；

然后，m 位老师同时可以移动到相邻格子，或保持不动。

这个过程会持续，直到老师抓住 David。当任意一位老师（可能不止一位）和 David 处于同一个格子时，David 就被抓住。

所有人都可以看到对方的移动，因此他们都会采取最优策略行动。

你的任务是，计算老师们在最优策略下需要多少次移动才能抓住 David。

David 会尽量延迟被抓时间；

老师们会合作，尽快将他抓住。

此外，Narek 和 Tsovak 认为这个问题太简单了，于是他们提出了 q 个关于 David 位置的查询。

输入格式

输入第一行为一个整数 t（1 ≤ t ≤ 10⁵）表示测试用例数量。

每个测试用例包含以下内容：

第一行三个整数 n, m, q（3 ≤ n ≤ 10⁹，1 ≤ m, q ≤ 10⁵）
分别表示格子的总数，老师的数量，以及查询数量。

第二行 m 个不同的整数 b₁, b₂, ..., bₘ（1 ≤ bᵢ ≤ n）
表示老师所在的格子编号。

第三行 q 个整数 a₁, a₂, ..., a_q（1 ≤ aⱼ ≤ n）
表示每次查询中 David 的初始位置。

保证：所有老师的位置和 David 的位置都互不相同。

保证：所有测试用例中 m 的总和不超过 2×10⁵，q 的总和不超过 2×10⁵。

输出格式

对于每个测试用例，输出 q 行，每行一个整数，表示 David 被抓住所需的最少移动次数。

样例输入

2
8 1 1
6
3
10 3 3
1 4 8
2 3 10

样例输出

5
1
1
2

样例说明

第一个测试用例中，David 处于格子 3，他可以跑到最左边的格子 1，然后老师从格子 6 到格子 1 需要 5 步，所以答案是 5。

第二个测试用例：

查询 1：David 在格子 2，老师中离他最近的是格子 1 或 4，只需 1 步。

查询 2：David 在格子 3，老师在格子 4，1 步就能抓到。

查询 3：David 在格子 10，最近老师在格子 8，老师从 8 到 10 需 2 步。