Consider the problem of computing (x1 x2 ... xn)/x1, (x1 x2 ... xn)/x2, ..., (x1 x2 ... xn)/xn given x1, x2, ..., xn. Assume that n is a power of 2. For example, for n = 4, the problem is to compute x2 x3 x4, x1 x3 x4, x1 x2 x4, x1 x2 x3, given x1, x2, x3, x4. State an algorithm that solves this problem using n^{1+o(1)} multiplications and no other x-dependent operations. State exactly how many multiplications the algorithm uses, as a function of n. Note that the time taken by the multiplications is not being counted. Cost in this problem is measured by the number of multiplications. Note also that divisions are not allowed.