CMPLS  Complete the Sequence!
You probably know those quizzes in Sunday magazines: given the sequence 1, 2, 3, 4, 5, what is the next number? Sometimes it is very easy to answer, sometimes it could be pretty hard. Because these "sequence problems" are very popular, ACM wants to implement them into the "Free Time" section of their new WAP portal.
ACM programmers have noticed that some of the quizzes can be solved by describing the sequence by polynomials. For example, the sequence 1, 2, 3, 4, 5 can be easily understood as a trivial polynomial. The next number is 6. But even more complex sequences, like 1, 2, 4, 7, 11, can be described by a polynomial. In this case, 1/2.n^{2}1/2.n+1 can be used. Note that even if the members of the sequence are integers, polynomial coefficients may be any real numbers.
Polynomial is an expression in the following form:
If a_{D} <> 0, the number D is called a degree of the polynomial. Note that constant function P(n) = C can be considered as polynomial of degree 0, and the zero function P(n) = 0 is usually defined to have degree 1.
Input
There is a single positive integer T on the first line of input (equal to about 5000). It stands for the number of test cases to follow. Each test case consists of two lines. First line of each test case contains two integer numbers S and C separated by a single space, 1 <= S < 100, 1 <= C < 100, (S+C) <= 100. The first number, S, stands for the length of the given sequence, the second number, C is the amount of numbers you are to find to complete the sequence.
The second line of each test case contains S integer numbers X_{1}, X_{2}, ... X_{S} separated by a space. These numbers form the given sequence. The sequence can always be described by a polynomial P(n) such that for every i, X_{i} = P(i). Among these polynomials, we can find the polynomial P_{min} with the lowest possible degree. This polynomial should be used for completing the sequence.
Output
For every test case, your program must print a single line containing C integer numbers, separated by a space. These numbers are the values completing the sequence according to the polynomial of the lowest possible degree. In other words, you are to print values P_{min}(S+1), P_{min}(S+2), .... P_{min}(S+C).
It is guaranteed that the results P_{min}(S+i) will be nonnegative and will fit into the standard integer type.
Example
Sample Input:
4 6 3 1 2 3 4 5 6 8 2 1 2 4 7 11 16 22 29 10 2 1 1 1 1 1 1 1 1 1 2 1 10 3
Sample Output:
7 8 9 37 46 11 56 3 3 3 3 3 3 3 3 3 3Warning: large Input/Output data, be careful with certain languages
hide comments
flyingduchman_:
20161119 19:52:36
Use difference method.


mredik5:
20160720 15:07:49
For me this problem is about finding the formula of polynomial Pmin that gives that output not to find . So basically you shouldnt care about the 3rd case just do a program that will give you the right answer. I can help some of you that the lowest possible digree of Pmin should not(i think it wont) be higher than C.


get_right_jr:
20160704 09:59:31
Easy problem


more_practice:
20160627 12:12:56
Try difference of method; in RECursion,it is of 3.13 sec and in iteration 0.05sec. 

Parikshit:
20160623 12:06:23
simple method of difference AC in one go.. 0.04 sec Last edit: 20160623 12:17:39 

Sarthak Munshi:
20160608 07:52:35
strange ! cannot figure out polynomial finite difference theorem for 3rd test case ! 

salvatore13:
20160418 23:07:12
i don't know but wolfram alpha knows in some magic way


ekranoplano:
20160408 23:38:47
Guys, It is possible to have some new test cases? Tnx 

nathanek:
20160225 13:20:39
guys im lost, i have used finite difference method and am getting the wrong answer. Any tips on test cases? 

layman806:
20160123 19:53:26
@enigmus , I used method of difference too, and I got it right in 0.15s on C++ 5.1 ! 
Added by:  adrian 
Date:  20040508 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  ACM Central European Programming Contest, Prague 2000 