Preliminaries for fast interpolation. Let R be a ring, let 0,1,,e1R, and 0,1,,e1R be given as input. The form of the Lagrange interpolation polynomial (4) suggests that one should first seek to construct the coefficients of the polynomial =i=0e1ij=0j=ie1(xj)R[x]. Show that we can compute the coefficients of in O(M(e)loge) operations in R. You may assume that e=2k for a nonnegative integer k. Here M(e)=elogelogloge. Hints: Work with binary strings and the representation of the perfect binary tree using binary strings in {0,1}k. To construct the coefficients of the polynomial (1), first construct a subproduct tree with polynomials su for all u{0,1}k from 0,1,,e1 as during fast evaluation. Next, annotate the tree with another family of polynomials such that the polynomial at the root will be equal to (1). You may want to try associating with each leaf v{0,1}k the polynomial v=v and with each internal node u{0,1}2k1 the polynomial u=u0su1+su0u1. Why is this a good choice? Prepare a small example, say with k=2 or k=3 as necessary. Show that =, where is the empty binary string