Let A[1..n] and B[1..n] be two sorted arrays. We can easily output the k-th smallest element in A in constant time by just outputting A[k]. Similarly, we can nd the k-th smallest element in B. Give a O(lg k) time divide-and-conquer algorithm to find the k-th smallest element overall { i.e., the k-th smallest in the union of A and B. Explain why your algorithm works. You can assume all elements in A and B are different.