D2. Красный свет, зелёный свет (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в ограничении на $$$k$$$ и общую сумму $$$n$$$ и $$$q$$$ по всем наборам входных данных. Вы можете делать взломы только тогда, когда обе версии задачи решены.

Вам дан отрезок длиной $$$10^{15}$$$ и константа $$$k$$$. Существует ровно $$$n$$$ ячеек, которые содержат светофор; каждая имеет позицию $$$p_i$$$ и начальную задержку $$$d_i$$$, для которой $$$d_i \lt k$$$. $$$i$$$-й светофор работает следующим образом:

  • он показывает красный свет на $$$l \cdot k + d_i$$$-й секунде, где $$$l$$$ — целое число,
  • в противном случае он показывает зеленый свет.

На $$$0$$$ секунде вы изначально находитесь в какой-то ячейке на отрезке и смотрите в положительном направлении. Каждую секунду вы выполняете следующие действия по порядку:

  • Если текущая ячейка содержит красный светофор, вы разворачиваетесь.
  • Вы перемещаетесь на одну ячейку в направлении, в котором вы сейчас смотрите.

Вам даны $$$q$$$ различных начальных позиций. Для каждой из них определите, покинете ли вы в конечном итоге отрезок в течение $$$10^{100}$$$ секунд.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k$$$ ($$$\mathbf{1 \le n \le 2\cdot10^5}$$$ и $$$\mathbf{1 \le k \le 10^{15}}$$$) — количество светофоров и длина периода.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots p_n$$$ ($$$1 \le p_1 \lt p_2 \lt \ldots \lt p_n \le 10^{15}$$$) — позиции светофоров.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$d_1, d_2, \ldots d_n$$$ ($$$0 \le d_i \lt k$$$) — задержки светофоров.

Четвёртая строка каждого набора входных данных содержит одно целое число $$$q$$$ ($$$\mathbf{1 \le q \le 2\cdot10^5}$$$) — количество запросов.

Пятая строка каждого набора входных данных содержит $$$q$$$ целых чисел $$$a_1, a_2, \ldots, a_q$$$ ($$$1 \leq a_i \leq 10^{15}$$$) — начальные позиции.

Гарантируется, что суммы $$$n$$$ и суммы $$$q$$$ по всем наборам входных данных не превосходят $$$\mathbf{2\cdot10^5}$$$.

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

Для каждого набора входных данных выведите $$$q$$$ строк. Каждая строка должна содержать «YES», если вы в конечном итоге покинете отрезок, и «NO», если нет. Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
4
2 2
1 4
1 0
3
1 2 3
9 4
1 2 3 4 5 6 7 8 9
3 2 1 0 1 3 3 1 1
5
2 5 6 7 8
4 2
1 2 3 4
0 0 0 0
4
1 2 3 4
3 4
1 2 3
3 1 1
3
1 2 3
Выходные данные
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
NO
NO
YES
NO
YES
Примечание

В первом наборе входных данных происходит следующее при начальных позициях $$$1$$$, $$$2$$$ и $$$3$$$:

А во втором наборе входных данных при начальной позиции $$$2$$$: