D. Two Arrays
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The median of the sequence $$$[s_1, s_2, \dots, s_k]$$$ is defined as the element that appears at position $$$\lfloor \frac{k+1}{2} \rfloor$$$ when the sequence is sorted in non-decreasing order. For example, the median of the sequence $$$[4, 5, 6, 1, 2, 2]$$$ is $$$2$$$; the median of the sequence $$$[3, 6, 3, 4, 5]$$$ is $$$4$$$.

You are given two arrays $$$[a_1, a_2, \dots, a_n]$$$ and $$$[b_1, b_2, \dots, b_m]$$$, sorted in non-decreasing order. Both arrays have odd lengths.

In one operation, you can do the following:

  • choose one of the arrays and mark an odd number of elements in it;
  • calculate $$$x$$$ — the median of the marked elements;
  • remove all marked elements;
  • insert $$$x$$$ into any position of the array on which the operation was performed.

Your task is to determine whether it is possible to make the arrays equal.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of three lines:

  • the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$);
  • the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$);
  • the third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_1 \le b_2 \le \dots \le b_m \le 10^9$$$).

Additional constraints on the input:

  • the sum of $$$(n+m)$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$;
  • in every test case, $$$n \bmod 2 = 1$$$ and $$$m \bmod 2 = 1$$$.
Output

For each test case, output YES if it is possible to make the arrays equal, or NO if it is not possible.

Example
Input
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
Output
YES
NO
YES
Note

In the first example, the arrays can be made equal by applying the following sequence of operations:

  1. for the array $$$a = [1, 2, 3, 4, 5]$$$, mark the $$$2$$$-nd, $$$4$$$-th, and $$$5$$$-th elements. Their median is $$$4$$$. We insert it at the end of the array, resulting in $$$a = [1, 3, 4]$$$;
  2. for the array $$$b = [1, 3, 7]$$$, mark all elements. Their median is $$$3$$$. We get the array $$$b = [3]$$$;
  3. for the array $$$a = [1, 3, 4]$$$, mark all elements. Their median is $$$3$$$. We get the array $$$a = [3]$$$;
  4. now the arrays $$$a$$$ and $$$b$$$ are equal.