Find the K-th Smallest Element in Two Sorted Arrays

Peter loves playing with sequences of numbers. He discovered an interesting game: given two sorted arrays A and B and an integer k, determine the k-th smallest element in the merged version of these two arrays without merging them explicitly. Use an efficient divide-and-conquer approach with a complexity of O(log(k)).

Note: The value k is 1-indexed. That is, k = 1 corresponds to the smallest element.

The relation can be stated in mathematical notation as follows: if L is the merged sorted array of A and B, find \(L[k-1]\).

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains two integers N and M, representing the number of elements in arrays A and B respectively.
• The second line contains N space-separated integers denoting the sorted array A. If N = 0, this line will be empty.
• The third line contains M space-separated integers denoting the sorted array B. If M = 0, this line will be empty.
• The fourth line contains an integer K, the position (1-indexed) of the required smallest element.

outputFormat

Output to standard output (stdout) a single integer representing the k-th smallest element in the combined sorted sequence of arrays A and B.

4 3
2 3 6 7
1 5 8
5

6