题目描述

这是这道题的困难版本。在该版本中，$m \leq 2\cdot 10^5$。

Skibidus 有两个数组 $a$ 和 $b$，分别包含 $n$ 个和 $m$ 个元素。对于 $1$ 到 $n$ 的每个整数 $i$，他最多可以执行一次以下操作：

• 选择一个整数 $j$（$1 \leq j \leq m$），将 $a_i$ 赋值为 $b_j - a_i$。注意，经过此操作后，$a_i$ 可能变为非正数。

Skibidus 需要你的帮助，判断是否可以通过若干次上述操作，使得数组 $a$ 为非递减序列。

$^{\text{∗}}$ 若 $a_1 \leq a_2 \leq \dots \leq a_n$，则数组 $a$ 为非递减序列。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq m \leq 2 \cdot 10^5$）。

接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）。

接下来一行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \leq b_i \leq 10^9$）。

保证所有测试用例中，$n$ 的总和以及 $m$ 的总和都不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果可以使 $a$ 按非递减顺序排列，则在新的一行输出 YES，否则输出 NO。

样例

5
1 3
5
9 1 1000000000
3 2
1 4 3
3 4
4 3
2 4 6 5
6 1 8
5 2
6 4 5 4 5
4 1000
3 1
9 8 7
8

YES
NO
YES
NO
YES

样例说明

• 在第一个测试用例中， $[5]$ 已经是非递减序列。
• 在第二个测试用例中，可以证明无法使其非递减。
• 在第三个测试用例中，我们可以将 $a_2$ 更新为 $b_1 - a_2 = 6 - 4 = 2$，将 $a_3$ 更新为 $b_3 - a_3 = 8 - 6 = 2$。此时数组变为 $[2,2,2,5]$，为非递减序列。
• 在最后一个测试用例中，我们可以对每个位置均执行操作，数组变为 $[-1,0,1]$，是非递减序列。

来源

Codeforces 2065C2，英文题名 Skibidus and Fanum Tax (hard version)。