D2. 红灯绿灯（困难版）

每个测试的时间限制：4 秒
内存限制：512 兆字节

这是本题的困难版本。唯一的区别在于 $k$ 的约束以及所有测试用例中 $n$ 和 $q$ 的总和不同。
只有同时解出本题的简单版本和困难版本，你才能进行hack。

---

题目描述

有一条长度为 $10^{15}$ 的条形道路，以及一个常数 $k$。
道路上恰好有 $n$ 个单元格装有交通信号灯；每个信号灯有一个位置 $p_i$ 和一个初始延迟 $d_i$，其中 $d_i < k$。

第 $i$ 个信号灯的工作方式如下：

• 在 $l \cdot k + d_i$ 秒时（其中 $l$ 是任意整数），该信号灯显示红灯；
• 其他时间显示绿灯。

在第 $0$ 秒时，你初始位于道路上的某个单元格，面向正方向。
在每一秒，你按如下顺序执行操作：

1. 如果当前单元格装有红灯，则转身（反向）；
2. 朝着你当前面向的方向移动一个单元格。

你有 $q$ 个不同的起始位置。对于每个起始位置，判断你是否会在 $10^{100}$ 秒内最终离开这条道路。

---

输入格式

每个测试包含多个测试用例。
第一行输入一个整数 $t$（$1 \le t \le 2 \cdot 10^5$），表示测试用例的数量。

每个测试用例的格式如下：

• 第一行输入两个整数 $n, k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^{15}$）——信号灯的数量和周期长度。
• 第二行输入 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_1 < p_2 < \dots < p_n \le 10^{15}$）——信号灯的位置。
• 第三行输入 $n$ 个整数 $d_1, d_2, \dots, d_n$（$0 \le d_i < k$）——信号灯的延迟。
• 第四行输入一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）——查询的数量。
• 第五行输入 $q$ 个整数 $a_1, a_2, \dots, a_q$（$1 \le a_i \le 10^{15}$）——起始位置。

保证所有测试用例的 $n$ 和 $q$ 的总和均不超过 $2 \cdot 10^5$。

---

输出格式

对于每个测试用例，输出 $q$ 行。
每行应包含 "YES" 或 "NO"，表示你是否会在 $10^{100}$ 秒内最终离开道路。
你可以以任意大小写输出答案（例如 "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$ 的过程如下所示（示意图原题有图，此处略）。