Find the K-th Smallest Element in Two Sorted Arrays

You are given two sorted arrays A and B and a positive integer k. Your task is to find the k-th smallest element in the merged sorted array of A and B.

The k-th smallest element is defined as the element at position \(k\) (1-indexed) when the two arrays are merged and sorted in non-decreasing order. For example, if the merged array is \(C = [c_1, c_2, \dots, c_{n_1+n_2}]\), you need to output \(c_k\).

It is guaranteed that \(1 \le k \le n_1+n_2\), where \(n_1\) and \(n_2\) are the sizes of the two arrays.

inputFormat

The input is read from stdin and has the following format:

n1 n2
A[0] A[1] ... A[n1-1]
B[0] B[1] ... B[n2-1]
k

Here, the first line contains two integers n1 and n2 representing the sizes of the two arrays. The second line contains n1 integers sorted in non-decreasing order, representing the first array. The third line contains n2 integers sorted in non-decreasing order, representing the second array. The fourth line contains a single integer k.

outputFormat

Output a single integer to stdout which is the k-th smallest element in the merged sorted array.

3 3
1 3 5
2 4 6
4

4