If S be a set of integers and x is an integer, the predecessor of x in S is defined to be the largest element of S that is x if such an integer exists, and otherwise. Consider the following problem: We are given a set S of integers, represented as a sorted list. We are also given a list Q of query values, which is also a sorted list. We want to output a list of pairs, where each query value is paired with its predecessor in S. As an example, if S = {2, 3, 5, 7, 11} and Q = [1, 3, 8, 9, 20], the output would be [(1, ),(3, 3),(8, 7),(9, 7),(20, 11)]. Describe an algorithm that solves this problem in O(n + k) worst-case time, where n is the number of items in the list Q and k is the number of elements in the set S.