D. Два массива
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Медианой последовательности $$$[s_1, s_2, \dots, s_k]$$$ назовем элемент, который окажется на позиции $$$\lfloor \frac{k+1}{2} \rfloor$$$, если отсортировать эту последовательность в неубывающем порядке. Например, медиана последовательности $$$[4, 5, 6, 1, 2, 2]$$$ — это $$$2$$$; медиана последовательности $$$[3, 6, 3, 4, 5]$$$ — это $$$4$$$.

Даны два массива $$$[a_1, a_2, \dots, a_n]$$$ и $$$[b_1, b_2, \dots, b_m]$$$, отсортированных в порядке неубывания. Длины обоих массивов нечетные.

За одну операцию вы можете сделать следующее:

  • выбрать один из массивов и отметить в нем нечетное количество элементов;
  • вычислить $$$x$$$ — медиану отмеченных элементов;
  • удалить все отмеченные элементы;
  • вставить $$$x$$$ в любую позицию того массива, над которым проводилась операция.

Ваша задача — определить, можно ли сделать массивы равными.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из трех строк:

  • первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$);
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$);
  • третья строка содержит $$$m$$$ целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_1 \le b_2 \le \dots \le b_m \le 10^9$$$).

Дополнительные ограничения на входные данные:

  • сумма $$$(n+m)$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$;
  • в каждом наборе входных данных $$$n \bmod 2 = 1$$$ и $$$m \bmod 2 = 1$$$.
Выходные данные

На каждый набор входных данных выведите YES, если можно сделать массивы равными, или NO, если нельзя.

Пример
Входные данные
3
5 3
1 2 3 4 5
1 3 7
3 5
11 17 19
19 20 26 29 37
1 7
11
1 2 7 9 11 15 17
Выходные данные
YES
NO
YES
Примечание

В первом примере можно сделать массивы одинаковыми, если применить следующую последовательность операций:

  1. для массива $$$a = [1, 2, 3, 4, 5]$$$ отметить $$$2$$$-й, $$$4$$$-й и $$$5$$$-й элементы. Их медиана равна $$$4$$$. Вставим ее в конец массива, получим $$$a = [1, 3, 4]$$$;
  2. для массива $$$b = [1, 3, 7]$$$ отметить все элементы. Их медиана равна $$$3$$$. Получим массив $$$b = [3]$$$;
  3. для массива $$$a = [1, 3, 4]$$$ отметить все элементы. Их медиана равна $$$3$$$. Получим массив $$$a = [3]$$$;
  4. теперь массивы $$$a$$$ и $$$b$$$ равны.