Consider two sets A and B, each having n integers in the range from 0 to 10n. We wish to compute the Cartesian sum of A and B, defined by:

C = {x + y : x A, y B}.

Note that integers in C are in the range from 0 to 20n. We want to find the set of elements in C and also the number of times each element of C is realized as a sum of elements in A and B. Show that the problem can be solved in O(n log(n)) time by reducing it to the polynomial multiplication algorithm. You just use the polynomial multiplication algorithm without modifying it. You need to explain what input you put into the polynomial multiplication algorithm and what you do with the output to get the solution to the Cartesian Sum problem.

Example: A = [1, 2, 3], B = [2, 3] and the solution to the Cartesian Sum problem is: C = [3, 4, 5, 6]

3 appears and is obtainable in 1 way,

4 appears and is obtainable in 2 ways,

5 appears and is obtainable in 2 ways,

6 appears and is obtainable in 1 way.