Let A[1..] 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 nd 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 dierent.