C2. Skibidus and Fanum Tax (hard version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is the hard version of the problem. In this version, $$$m \leq 2\cdot 10^5$$$.Skibidus has obtained two arrays $$$a$$$ and $$$b$$$, containing $$$n$$$ and $$$m$$$ elements respectively. For each integer $$$i$$$ from $$$1$$$ to $$$n$$$, he is allowed to perform the operation at most once: Choose an integer $$$j$$$ such that $$$1 \leq j \leq m$$$. Set $$$a_i := b_j - a_i$$$. Note that $$$a_i$$$ may become non-positive as a result of this operation. Skibidus needs your help determining whether he can sort $$$a$$$ in non-decreasing order$$$^{\text{∗}}$$$ by performing the above operation some number of times.$$$^{\text{∗}}$$$$$$a$$$ is sorted in non-decreasing order if $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$.InputThe first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 2\cdot 10^5$$$).The following line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).The following line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.OutputFor each test case, if it is possible to sort $$$a$$$ in non-decreasing order, print "YES" on a new line. Otherwise, print "NO" on a new line.You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" will also be recognized as positive responses.ExampleInput51 359 1 10000000003 21 4 33 44 32 4 6 56 1 85 26 4 5 4 54 10003 19 8 78OutputYES
NO
YES
NO
YES
NoteIn the first test case, $$$[5]$$$ is already sorted.In the second test case, it can be shown that it is impossible.In the third test case, we can set $$$a_2:=b_1-a_2=6-4=2$$$ and $$$a_3:=b_3-a_3=8-6=2$$$. The sequence $$$[2,2,2,5]$$$ is in nondecreasing order.In the last case, we can apply operations on each index. The sequence becomes $$$[-1,0,1]$$$, which is in nondecreasing order.