Progressions

All submissions for this problem are available.
Do you remember those questions of Sequence and Series chapter of Class 11th in which we were required to find the next number of a particular sequence? If not then let us revise a few concepts first.
The sequences can be generally described by polynomials. For e.g. 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, 1/2.n^{2}1/2.n+1 . 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:
P(n) = a_{k}.n^{k}+a_{k1}.n^{k1}+...+a_{1}.n+a_{0}
If a_{k} != 0, the number k is called a degree of the polynomial. Note that a constant function of the form P(n) = C is of degree 0, and the zero function P(n) = 0 is of degree 1.
Input
There are multiple test cases in the input. The input begins with a single integer which gives the number of test cases. Each test case consists of two lines. First line of each test case contains two integers L and Q separated by a space, 1 ≤ L < 100, 1 ≤ Q < 100, (L+Q) ≤ 100. Here L is the length of the given sequence and Q is the amount of numbers you are required to find to complete the sequence.
The second line of each test case contains L integer numbers Z_{1}, Z_{2}, ..., Z_{L} separated by a space. These numbers form the given sequence and it can be described by a polynomial P(n) such that for every x, Z_{x} = P(x). Among these polynomials, we can find the polynomial Pmin with the lowest possible degree which is the required polynomial to be used for completing the sequence.
Output
For every test case, print Q integer numbers, which are the values completing the sequence according to the polynomial Pmin, separated by a space, i.e. you need to print Pmin(L+1), Pmin(L+2), ... , Pmin(L+Q).
It is guaranteed that the results Pmin(L+x) will be nonnegative integers.
Example
Input: 4 4 4 1 2 3 4 3 4 1 2 4 13 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 9 7 Output: 5 6 7 8 7 11 16 22 14 92 7 7 7 7 7 7 7 7 7
Author:  ajitesh14 
Tags  ajitesh14 
Date Added:  24102010 
Time Limit:  0.259206 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 