C. Выбери различные!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны массив $$$a$$$ из $$$n$$$ целых чисел, массив $$$b$$$ из $$$m$$$ целых чисел и чётное число $$$k$$$.

Ваша задача определить, возможно ли выбрать ровно $$$\frac{k}{2}$$$ элементов из обоих массивов так, чтобы среди выбранных элементов встречалось каждое целое число от $$$1$$$ до $$$k$$$.

Например:

  • Если $$$a=[2, 3, 8, 5, 6, 5]$$$, $$$b=[1, 3, 4, 10, 5]$$$, $$$k=6$$$, то можно выбрать элементы со значениями $$$2, 3, 6$$$ из массива $$$a$$$ и элементы со значениями $$$1, 4, 5$$$ из массива $$$b$$$. В таком случае, среди выбранных элементов будут встречаться все числа от $$$1$$$ до $$$k=6$$$.
  • Если $$$a=[2, 3, 4, 5, 6, 5]$$$, $$$b=[1, 3, 8, 10, 3]$$$, $$$k=6$$$, то выбрать элементы таким образом невозможно.

Обратите внимание, что от вас не требуется найти способ выбора элементов — ваша программа должна лишь проверять, возможно ли выбрать элементы требуемым образом.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 2\cdot10^5$$$, $$$2 \le k \le 2 \cdot \min(n, m)$$$, $$$k$$$ — чётное число) — длину массива $$$a$$$, длину массива $$$b$$$ и количество элементов, которое нужно выбрать, соответственно.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива $$$a$$$.

Третья строка каждого набора содержит $$$m$$$ целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_j \le 10^6$$$) — элементы массива $$$b$$$.

Гарантируется, что сумма значений $$$n$$$ и $$$m$$$ по всем наборам входных данных теста не превосходит $$$4 \cdot 10^5$$$.

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

Выведите $$$t$$$ строк, каждая из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите «YES», если существует способ выбрать по $$$\frac{k}{2}$$$ чисел из каждого массива так, чтобы среди выбранных элементов встречалось каждое целочисленное значение от $$$1$$$ до $$$k$$$. Иначе выведите «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
6
6 5 6
2 3 8 5 6 5
1 3 4 10 5
6 5 6
2 3 4 5 6 5
1 3 8 10 3
3 3 4
1 3 5
2 4 6
2 5 4
1 4
7 3 4 4 2
1 4 2
2
6 4 4 2
1 5 2
3
2 2 1 4 3
Выходные данные
YES
NO
YES
YES
NO
NO
Примечание

В первом наборе входных данных примера можно выбрать элементы, равные $$$2$$$, $$$3$$$ и $$$6$$$ из массива $$$a$$$ и элементы равные $$$1$$$, $$$4$$$ и $$$5$$$ из массива $$$b$$$. Таким образом, среди выбранных элементов встречается каждое число от $$$1$$$ до $$$k=6$$$.

Во втором наборе входных данных примера можно показать, что выбрать ровно три элемента из каждого массива требуемым образом невозможно.

В третьем наборе входных данных примера можно выбрать элементы, равные $$$1$$$ и $$$3$$$ из массива $$$a$$$ и элементы равные $$$2$$$ и $$$4$$$ из массива $$$b$$$. Таким образом, среди выбранных элементов встречается каждое число от $$$1$$$ до $$$k=4$$$.