题目描述

你可能知道那些周日杂志上的小测验：给定一个序列1, 2, 3, 4, 5，下一个数字是什么？有时候答案非常简单，有时候却可能相当困难。由于这些“序列问题”非常受欢迎，ACM（国际计算机学会）希望将它们引入其新WAP门户的“自由时间”板块。

ACM的程序员们注意到，有些测验可以通过多项式来描述序列。例如，序列1, 2, 3, 4, 5可以很容易地理解为一个简单的多项式，下一个数字是6。但即使是更复杂的序列，比如1, 2, 4, 7, 11，也可以用多项式来描述。在这种情况下，可以使用多项式$P(n) = \frac{1}{2}n^2 - \frac{1}{2}n + 1$。需要注意的是，即使序列中的成员是整数，多项式的系数也可以是任意实数。

多项式的形式如下：

$P(n) = a_D \cdot n^D + a_{D-1} \cdot n^{D-1} + \ldots + a_1 \cdot n + a_0$

如果$a_D \neq 0$，则数字$D$称为多项式的次数。注意，常数函数$P(n) = C$可以被视为次数为0的多项式，而零函数$P(n) = 0$通常被定义为次数为-1。

输入格式

输入的第一行是一个正整数$T$，表示测试用例的数量。每个测试用例由两行组成： • 第一行是两个整数$S$和$C$，用空格分隔，满足$1 \leq S < 100$，$1 \leq C < 100$，且$(S + C) \leq 100$。$S$表示给定序列的长度，$C$表示需要补充的序列数字的数量。

• 第二行是$S$个整数$X_1, X_2, \ldots, X_S$，用空格分隔。这些数字构成给定的序列。该序列总能被一个多项式$P(n)$描述，使得对于每个$i$，$X_i = P(i)$。在这些多项式中，我们可以找到一个次数最低的多项式$P_{\text{min}}$，这个多项式应该用于补充序列。

输出格式

对于每个测试用例，输出一行，包含$C$个整数，用空格分隔。这些数字是根据最低次数多项式补充的序列值。换句话说，你需要输出 $P_{\text{min}}(S+1), P_{\text{min}}(S+2), \ldots, P_{\text{min}}(S+C)$。

题目保证结果$P_{\text{min}}(S+i)$是非负的，并且在标准整数类型范围内。

示例输入

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

示例输出

7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3

题目来源 Central Europe 2000