C2. Скибидус и Fanum tax (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии $$$m \leq 2\cdot 10^5$$$.

Скибидус получил два массива $$$a$$$ и $$$b$$$, содержащие соответственно $$$n$$$ и $$$m$$$ элементов. Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n$$$ ему разрешено выполнить операцию не более одного раза:

  • Выбрать целое число $$$j$$$ такое, что $$$1 \leq j \leq m$$$. Присвоить $$$a_i := b_j - a_i$$$. Обратите внимание, что в результате этой операции $$$a_i$$$ может стать неположительным.

Скибидус нуждается в вашей помощи, чтобы определить, может ли он отсортировать $$$a$$$ в неубывающем порядке$$$^{\text{∗}}$$$ выполнив вышеуказанную операцию некоторое количество раз.

$$$^{\text{∗}}$$$$$$a$$$ отсортирован в неубывающем порядке, если $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$.

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

Первая строка содержит целое число $$$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» также будут распознаны как положительные ответы.

Пример
Входные данные
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]$$$, которая отсортирована в неубывающем порядке.