E. Найти машину
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тимур находится в машине, двигающейся по числовой прямой от точки $$$0$$$ до точки $$$n$$$. Машина начинает движение из точки $$$0$$$ в минуту $$$0$$$.

На прямой находится $$$k+1$$$ знак в точках $$$0, a_1, a_2, \dots, a_k$$$, и Тимур знает, что машина прибудет туда в минуты $$$0, b_1, b_2, \dots, b_k$$$ соответственно. Последовательности $$$a$$$ и $$$b$$$ возрастающие, причем $$$a_k = n$$$.

Машина движется с постоянной скоростью между любыми двумя соседними знаками. У Тимура есть $$$q$$$ запросов: каждый запрос будет целым числом $$$d$$$, и Тимур хочет, чтобы вы вывели, сколько минут машина затратит, чтобы добраться до точки $$$d$$$, округленное в меньшую сторону.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$k$$$ и $$$q$$$, ($$$k \leq n \leq 10^9$$$; $$$1 \leq k, q \leq 10^5$$$) — конечное местоположение, количество точек, для которых Тимур знает время, и количество запросов соответственно.

Вторая строка каждого набора содержит $$$k$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq n$$$; $$$a_i < a_{i+1}$$$ для каждого $$$1 \leq i \leq k-1$$$; $$$a_k = n$$$).

Третья строка каждого набора содержит $$$k$$$ целых чисел $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$; $$$b_i < b_{i+1}$$$ для каждого $$$1 \leq i \leq k-1$$$).

Каждая из следующих $$$q$$$ строк содержит одно целое число $$$d$$$ ($$$0 \leq d \leq n$$$) — расстояние, для которого Тимур запрашивает количество минут.

Гарантируется, что сумма $$$k$$$ по всем наборам не превышает $$$10^5$$$, и сумма $$$q$$$ по всем наборам не превышает $$$10^5$$$.

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

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

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

В первом примере машина проходит от точки $$$0$$$ до точки $$$10$$$ за $$$10$$$ минут, поэтому скорость составляет $$$1$$$ единицу в минуту и:

  • В точке $$$0$$$ время будет $$$0$$$ минут.
  • В точке $$$6$$$ время будет $$$6$$$ минут.
  • В точке $$$7$$$ время будет $$$7$$$ минут.

Во втором примере машина движется со скоростью $$$1$$$ единицу в минуту между точками $$$0$$$ и $$$4$$$, и со скоростью $$$2$$$ единицы в минуту между $$$4$$$ и $$$10$$$ и:

  • В точке $$$6$$$ время будет $$$5$$$ минут.
  • В точке $$$4$$$ время будет $$$4$$$ минут.
  • В точке $$$2$$$ время будет $$$2$$$ минут.
  • В точке $$$7$$$ время будет $$$5.5$$$ минут, поэтому ответ — $$$5$$$.

В четвёртом примере машина движется со скоростью $$$1.2$$$ единицы в минуту, поэтому ответы на запросы:

  • В точке $$$2$$$ время будет $$$1.66\dots$$$ минут, поэтому ответ — $$$1$$$.
  • В точке $$$6$$$ время будет $$$5$$$ минут.
  • В точке $$$5$$$ время будет $$$4.16\dots$$$ минут, поэтому ответ — $$$4$$$.