K-th Smallest From Two Merged Sorted Arrays

You are given two arrays A and B, each already sorted in non-decreasing order, and a 1-indexed position k. Consider merging A and B into one non-decreasing sequence (keeping duplicates). Output the value at position k of that merged sequence — that is, the k-th smallest value of the combined multiset.

You do not need to materialize the merged array: walk both arrays with two pointers, always taking the smaller front element, and stop after k elements have been taken.

Input format

Line 1: three integers n, m, k separated by spaces — the length of , the length of , and the 1-indexed position. Line 2: space-separated integers, array in non-decreasing order (empty when ). Line 3: space-separated integers, array in non-decreasing order (empty when ).

Output format

A single integer: the k-th smallest value of the merged multiset.

Constraints

• 0 ≤ n, m ≤ 100000
• 1 ≤ k ≤ n + m (so at least one array is non-empty and k is a valid position)
• -1000000000 ≤ each value ≤ 1000000000
• Both A and B are guaranteed to be sorted in non-decreasing order.