UVA1546 Complete the sequence!

# Complete the sequence! [problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4321 [PDF](https://uva.onlinejudge.org/external/15/p1546.pdf)  你可能知道那些在周日杂志中的谜题：给你一个由数字 1,2,3,4,5 组成的序列，下一个数字是什么？有时它很容易被解答，有时也会非常困难。因为这些“序列问题”非常有名，ACM想要在他们的新WAP网站的“空闲时间”部分中实装。 ACM的程序员们注意到一些谜题可以通过用多项式描述序列来解决。比如，序列 1,2,3,4,5 可以被轻松地用一个简单的多项式描述。下一个数字是 6。但更为复杂的序列，比如序列 1,2,4,7,11，可以被多项式 $\frac{1}{2} n^2 - \frac{1}{2}n + 1 $ 描述。请注意，尽管序列中的数字都是整数，多项式中各项的系数可以为任意实数。 多项式是一种如下格式的表达式: $$P(n) = a_Dn^D + a_{D-1}n^{D-1} + \cdots + a_1n + a_0$$ 如果 $a_D \ne 0$，则数字 $D$ 被称为多项式的一个次数。请注意，常值函数 $P(n) = C$ 可以被认为是一个次数为 0 的多项式，零值函数 $P(n) = 0$ 通常被定义为次数为 -1.

 第一行为一个整数 $T$，为测试数据组数 每组测试数据中包含两行输入。第一行为用一个空格分开的两个整数 $S(1 \le S \le 100),C(1 \le C \le 100),(S + C) \le 100$，第一个整数 $S$ 为接下来所给出的序列长度，第二个整数 $C$ 为你所需要在原序列后填上的后续数字数量。 第二行为一段包含 $S$ 个用一个空格分开的整数 $X_1,X_2,\cdots,X_S$。这些整数构成了给出的序列。给出的序列可以被多项式 $P(n)$ 所描述，即对于每一个 $i$，$X_i = P(i)$。在这些多项式中，我们可以找到次数最低的多项式 $P_{min}$(译者注：一个多项式的次数定义为每项次数的最大值)。这个多项式应可以被用来完成原序列。

 对于每一组测试数据，你需要先输出 $C$ 个用一个空格分开的整数。这些整数为可能的次数最低的多项式所计算出的原序列的后续数字。换而言之，你需要输出 $P_{min}(S+1),P_{min}(S+2),\cdots,P_{min}(S+C)$。 保证 $P_{min}(S+i)$ 的值为非负整数，且不超过 int 整数范围。 ## 样例 #1 ### 样例输入 #1 ``` 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 ``` ### 样例输出 #1 ``` 7 8 9 37 46 11 56 3 3 3 3 3 3 3 3 3 3 ```