H. Prefix MEX
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$ of non-negative integers.

The array $$$a$$$ has length $$$n$$$, and the array $$$b$$$ has length $$$m$$$.

You are also given an integer $$$k$$$.

You have to choose a non-empty prefix of $$$a$$$ and a non-empty prefix of $$$b$$$.

Let $$$S$$$ be the set of all values that appear in the two chosen prefixes.

Your task is to determine whether it is possible to choose the two prefixes such that $$$\mathrm{mex}(S) = k$$$.

The $$$\mathrm{mex}$$$ of a set is the smallest non-negative integer that does not belong to the set.

Input

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

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$) — the length of array $$$a$$$, the length of array $$$b$$$, and the required MEX, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$0 \le b_i \le 10^9$$$).

It is guaranteed that the sum of $$$n + m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, print YES if it is possible to choose a non-empty prefix of $$$a$$$ and a non-empty prefix of $$$b$$$ such that the MEX of the set of chosen values is equal to $$$k$$$.

Otherwise, print NO.

You can print each letter in any case. For example, YES, Yes, and yes will all be accepted.

Example
Input
4
3 3 2
0 7 5
1 8 9
3 2 2
0 2 1
3 4
2 3 0
5 6
7 8 9
4 3 3
0 1 2 4
5 6 7
Output
YES
NO
YES
YES