Alice 和 Bob 是好朋友。在一堂关于解方程的数学课后，他们进行了一次简短的交谈。

Alice：解方程很简单。 Bob：我不信。$x^2 - x - 2 = 0$ 的根是什么？ Alice：太简单了。$-1$ 和 $2$ 是它的根。 Bob：那 $x^3 + 2x - x + 1 = 0$ 呢？ Alice：实根是 $\frac{\sqrt[3]{2(\sqrt{93}-9)}-2\sqrt[3]{\frac{3}{\sqrt{93}-9}}}{6^{\frac{2}{3}}}$。复根也很容易解。 Bob：难以置信！你真的很擅长解方程。现在我有一个挑战给你。考虑方程 $x^2 - x - 2 = 0$，你能构造一个新的二次方程，使得它的根是 $(-1)^2$ 和 $2^2$ 吗？ Alice：（几秒钟后）是 $x^2 - 5x + 4 = 0$。 Bob：太棒了。

当 Bob 回到宿舍时，他问了他的室友（也就是你）同样的问题。既然你有一台电脑并且擅长编程，你需要解决一个更具挑战性的问题。

给定一个整数 $m$ 和一个方程 $x^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 = 0$，其中根（包括实根和复根）为 $x_1, \dots, x_n$，你能构造一个新的方程 $y^n + b_{n-1}y^{n-1} + \dots + b_1y + b_0 = 0$，使得它的根为 $y_1, \dots, y_n$ 且满足 $y_1 = x_1^m, \dots, y_n = x_n^m$ 吗？

输入格式

最多有 15 组测试数据。

每组测试数据包含两行输入。 第一行包含两个整数 $n$ 和 $m$。 第二行包含 $n$ 个整数 $a_0, \dots, a_{n-1}$，它们是方程 $x^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 = 0$ 的系数。

输入以一行两个 0 结束。

数据保证 $n, m \ge 1$，$n \le 6$，$n + m \le 10$，$|a_i| \le 120$。

输出格式

对于每组测试数据，输出一行整数 $b_0, \dots, b_{n-1}$，描述方程 $y^n + b_{n-1}y^{n-1} + \dots + b_1y + b_0 = 0$。

数据保证 $|b_i| < 10^{12}$。

样例

样例输入 1

1 9
2
2 2
2 -3
2 2
2 -1
0 0

样例输出 1

512
4 -5
4 3

说明

在第一组测试数据中，Bob 给出的方程是 $x + 2 = 0$，其根为 $-2$。对应的方程是 $x + 512 = 0$，其根为 $(-2)^9$。

在第二组测试数据中，Bob 给出的方程是 $x^2 - 3x + 2 = 0$，其根为 $1$ 和 $2$。对应的方程是 $x^2 - 5x + 4 = 0$，其根为 $1^2$ 和 $2^2$。

在第三组测试数据中，Bob 给出的方程是 $x^2 - x + 2 = 0$，其根为 $\frac{1}{2}(1 \pm \sqrt{7}i)$。对应的方程是 $x^2 + 3x + 4 = 0$，其根为 $\frac{1}{2}(-3 \pm \sqrt{7}i)$。