Find the K-th Element in Merged Sorted Arrays

You are given two sorted arrays A and B of sizes N and M respectively, and an integer K (1-indexed). Your task is to find the K-th element of the merged sorted array formed by combining both A and B.

The arrays are sorted in non-decreasing order. Formally, if we denote the merged sorted array as C, then you need to determine C[K] where

$1 \le K \le N + M$

An efficient solution with a time complexity better than O(N+M) can be achieved using a binary search on partitions.

inputFormat

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

1. The first line contains three integers: N, M, and K.
2. The second line contains N integers representing the sorted array A.
3. The third line contains M integers representing the sorted array B.

It is guaranteed that 1 \le K \le N + M.

outputFormat

Output a single integer to stdout: the K-th element of the merged sorted array.

3 4 5
2 3 6
1 4 5 8

5