这是问题的困难版本。在此版本中,$$$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{*}}$$$。
输入
第一行包含一个整数 $$$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, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。
每个测试用例的以下行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果可以按非降序对 $$$a$$$ 进行排序,则在新行上打印“YES”。否则,在新行上打印“NO”。
任何情况下都可以输出答案。例如,字符串“yEs”、“yes”和“Yes”也将被识别为肯定响应。
示例
输入 #1
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
输出 #1
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]$$$,按非降序排列。