题目描述

给定两个长度为 $n$ 的数组 $a$ 和 $b$。

你可以任选 $k \in [0,n]$，将 $a$ 的前 $k$ 个元素和 $b$ 的后 $n-k$ 个元素拼接成一个长度为 $n$ 的新数组。

请从新数组中选出恰好 $m$ 个互不相邻的元素。记其中最小的元素为 $p$ ，求 $p$ 的最大值。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的数量。

每组测试数据第一行输入两个整数 $n$ 和 $m$ ($1 \le m \le \lceil \frac{n}{2} \rceil \le n \le 2 \times 10^5$)，分别表示数组长度和需要选择的元素数量。

第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示数组 $a$。

第三行输入 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$)，表示数组 $b$。

保证所有测试数据的 $\sum n \le 2 \times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示 $p$ 的最大值。

2
5 2
5 4 3 2 1
1 2 3 4 5
9 5
-1 1 -4 -5 -1 4 -1 -9 1
-9 -9 -8 2 4 -4 -3 -5 3

5
-4

提示

对于第 $1$ 组测试数据，当 $k = 4$ 时，新数组为 $[5, 4, 3, 2, 5]$，选择第 $1,5$ 个元素，最小元素为 $5$，可以证明这是最大值。