D. Flower Boy
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Flower boy has a garden of $$$n$$$ flowers that can be represented as an integer sequence $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the beauty of the $$$i$$$-th flower from the left.

Igor wants to collect exactly $$$m$$$ flowers. To do so, he will walk the garden from left to right and choose whether to collect the flower at his current position. The $$$i$$$-th flower among ones he collects must have a beauty of at least $$$b_i$$$.

Igor noticed that it might be impossible to collect $$$m$$$ flowers that satisfy his beauty requirements, so before he starts collecting flowers, he can pick any integer $$$k$$$ and use his magic wand to grow a new flower with beauty $$$k$$$ and place it anywhere in the garden (between two flowers, before the first flower, or after the last flower). Because his magic abilities are limited, he may do this at most once.

Output the minimum integer $$$k$$$ Igor must pick when he performs the aforementioned operation to ensure that he can collect $$$m$$$ flowers. If he can collect $$$m$$$ flowers without using the operation, output $$$0$$$. If it is impossible to collect $$$m$$$ flowers despite using the operation, output $$$-1$$$.

Input

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

The first line of each test case contains exactly two integers $$$n$$$ and $$$m$$$ $$$(1 \le m \le n \le 2 \cdot 10^5)$$$ — the number of flowers in the garden and the number of flowers Igor wants to collect, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — where $$$a_i$$$ is the beauty of the $$$i$$$-th flower from the left in the garden.

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, ..., b_m$$$ $$$(1 \le b_i \le 10^9)$$$ — where $$$b_i$$$ is the minimum beauty the $$$i$$$-th flower must have that Igor will collect.

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

Output

For each test case, on a separate line, output the minimum integer $$$k$$$ Igor must pick when he performs the aforementioned operation to ensure that he can collect $$$m$$$ flowers. If he can collect $$$m$$$ flowers without using the operation, output $$$0$$$. If it is impossible to collect $$$m$$$ flowers despite using the operation, output $$$-1$$$.

Example
Input
7
9 5
3 5 2 3 3 5 8 1 2
4 6 2 4 6
6 3
1 2 6 8 2 1
5 4 3
5 3
4 3 5 4 3
7 4 5
6 3
8 4 2 1 2 5
6 1 4
5 5
1 2 3 4 5
5 4 3 2 1
6 3
1 2 3 4 5 6
9 8 7
5 5
7 7 6 7 7
7 7 7 7 7
Output
6
3
7
0
-1
-1
7
Note

In the first test case, suppose Igor grows a flower of beauty $$$6$$$ and places it between the third and the fourth flowers. Then, the garden will look like the following: $$$[3, 5, 2, 6, 3, 3, 5, 8, 1, 2]$$$. Then, he can select the second, fourth, sixth, seventh, and eighth flowers with beauties $$$[5, 6, 3, 5, 8]$$$.

In the third test case, he can grow a flower of beauty $$$7$$$ and place it before the first flower. The garden will look like the following: $$$[7, 4, 3, 5, 4, 3]$$$. Now, he can choose the first, second, and fourth flowers.

In the fourth test case, Igor does not need to use the operation, so the answer is $$$0$$$.

In the sixth test case, no matter how Igor performs the operation, he cannot collect $$$3$$$ flowers such that the $$$i$$$-th flower he collects has a beauty of at least $$$b_i$$$, therefore the answer is $$$-1$$$.