Find the K-th Element in the Merged Sorted Array

Given two sorted arrays \(A\) and \(B\) of lengths n and m, respectively, and a positive integer k, your task is to find the k-th smallest element in the union of these two arrays when merged (i.e. the merged array is sorted in non-decreasing order).

Note: It is guaranteed that 1 \(\leq k \leq n + m\).

The expected time complexity should be better than O(n+m). One common approach to achieve this is to use a binary search algorithm.

The k-th smallest element is defined in a 1-indexed manner. For example, if \(A = [2, 3, 6, 7, 9]\) and \(B = [1, 4, 8, 10]\), and k = 5, the merged array is [1, 2, 3, 4, 6, 7, 8, 9, 10], so the answer is 6.

Mathematically, if we define the function kthElement(A, B, k), you are required to find the element satisfying:

[ \text{kthElement}(A,B,k) = \max\left({x \in A \cup B \mid #{y \in A \cup B : y \leq x} < k}\right) ]

inputFormat

The input is given through standard input (stdin) and is organized as follows:

• The first line contains two space-separated integers n and m, the sizes of the two arrays.
• The second line contains n space-separated integers representing array A (sorted in non-decreasing order).
• The third line contains m space-separated integers representing array B (sorted in non-decreasing order).
• The fourth line contains a single integer k (the position of the element to be found in the merged sorted order, 1-indexed).

outputFormat

Output the k-th smallest element in the merged array on standard output (stdout).

## sample

5 4
2 3 6 7 9
1 4 8 10
5

6