The Income-Tax Department had prepared a list D of names of defaulters on March $31$. However, the government extended the deadline to pay taxes till April $15$.
The IT department has now received two additional lists of names: a list B of names of people who have paid their taxes between April $1$ and April $15$ at a bank, and a list O of names of people have paid their taxes during this period online. Some people have paid part of their taxes at a bank and part online, so there may be names that appear in both B and O.
From the lists D, B and O, the IT department wants to prepare a revised list of defaulters. The names in the original list D are sorted in alphabetical order while the names in B and O are listed according to the date on which they paid their taxes. Fortunately, no two people have the same name.
Describe an efficient algorithm to compute the revised list of defaulters. Assume that the size of D, B and O is n, m and k respectively and that $n > m > k$. Describe the running time of your algorithm in terms of these parameters.