B2. Строгая учительница (сложная версия)
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственные отличия между двумя версиями заключаются в ограничениях на $$$m$$$ и $$$q$$$. В этой версии $$$m, q \le 10^5$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Нарек и Цовак были заняты подготовкой этого раунда, поэтому они не успели сделать домашнее задание, и они решили украсть домашнее задание Давида. Их строгая учительница заметила, что у Давида нет домашнего задания, и теперь хочет его наказать. Она наняла других учительниц, чтобы помочь поймать Давида, и теперь $$$m$$$ учительниц вместе преследуют его. К счастью, они находятся в большом классе, поэтому у Давида есть много мест, где можно спрятаться.

Класс можно представить как последовательность клеток, пронумерованных от $$$1$$$ до $$$n$$$, расположенных на прямой.

Изначально все $$$m$$$ учительниц и Давид находятся в различных клетках. Затем они делают ходы. Во время каждого хода:

  • Давид перемещается в соседнюю клетку или остается в текущей.
  • Затем каждая из $$$m$$$ учительниц одновременно перемещается в соседнюю клетку или остается в текущей.

Процесс продолжается, пока Давид не будет пойман. Давид пойман, если любая из учительниц (возможно, более одной) находится в той же клетке, что и Давид. Все участники видят ходы других, поэтому все действуют оптимально.

Ваша задача — посчитать, сколько ходов потребуется учительницам, чтобы поймать Давида, если они все действуют оптимально.

Оптимальность действий означает, что ученик делает свои ходы так, чтобы максимизировать количество ходов, необходимых учительницам, чтобы поймать его. А учительницы координируются друг с другом, чтобы сделать свои ходы так, чтобы минимизировать количество ходов, необходимых для поимки ученика.

Кроме того, поскольку Нарек и Цовак считают эту задачу простой, они решили задать вам $$$q$$$ запросов о положении Давида.

Входные данные

В первой строке входных данных вам дано одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание каждого набора входных данных.

В первой строке каждого набора входных данных вам даны три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$3 \le n \le 10^9$$$, $$$1 \le m, q \le 10^5$$$) — количество клеток на линии, количество учительниц и количество запросов.

Во второй строке каждого набора входных данных вам даны $$$m$$$ различных целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le n$$$) — номера клеток учительниц.

В третьей строке каждого набора входных данных вам даны $$$q$$$ целых чисел $$$a_1, a_2, \ldots, a_q$$$ ($$$1 \le a_i \le n$$$) — номера клеток Давида для каждого запроса.

Гарантируется, что для любого $$$i$$$, $$$j$$$ такие, что $$$1 \le i \le m$$$ и $$$1 \le j \le q$$$, $$$b_i \neq a_j$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ строк, в $$$i$$$-й из которых содержится ответ на $$$i$$$-й запрос.

Пример
Входные данные
2
8 1 1
6
3
10 3 3
1 4 8
2 3 10
Выходные данные
5
1
1
2
Примечание

В единственном запросе первого примера ученик может убежать в клетку $$$1$$$. Учительнице потребуется пять ходов, чтобы добраться из клетки $$$6$$$ до клетки $$$1$$$, поэтому ответ — $$$5$$$.

Во втором запросе второго примера ученик может просто остаться в клетке $$$3$$$. Учительница, изначально находящаяся в клетке $$$4$$$, может добраться до клетки $$$3$$$ за один ход. Следовательно, ответ — $$$1$$$.