Given a list of integers a1, a2, …, ak (k ≥ 2) and a positive integer m, write a function or a complete program that calculates the next m numbers of the list. Assume that ai = P(i) where
P(x) = bk-1 xk-1 + bk-2 xk-2 + … + b0
is the unique polynomial of minimum order which fits the points.
If the code is a function, input is given by an integer k, an array a1, a2, …, ak and an integer m.
If the code is a program, input (through stdin) is given by space-separated k a1 a2 … ak m.
You can assume that k ≥ 2 and m > 0.
(Of course, the code can calculate the result in different way, but the result should be same.)
Find the polynomial P(x) which satisfies ai = P(i) for all 1 ≤ i ≤ k and has a degree of (no more than) k - 1. For example, if a list is
1,2,3,4,5, then P(x) = x. If a list is
1,4,9,16,25, then P(x) = x2.
Then, calculate ak+1 = P(k+1), ak+2 = P(k+2), …, ak+m = P(k+m). These are the results.
If the code is a function, return an array [ak+1, ak+2, …, ak+m].
If the code is a full program, print those numbers to stdout, separated by an any character you want.