提示: 欢迎访问OurACM平台。
Problem 2017 Hwh’s Problem

Accept: 34    Submit: 85
Time Limit: 5000 mSec    Memory Limit : 32768 KB

Problem Description

Polynomial is an expression of more than two algebraic terms, esp. the sum of several terms that contain different powers of the same variable(s).

For example, G( p ) = 7 + 6g^1 + 2g^2 + 0g^3 + 113g^4 is an expression.

Hwh is one “SB” ( short for “ShenBen” ) and he always love math!In this problem, you are expected to calculate the coefficients of the polynomial S(g) = G(p)^m, here m is an integer larger than zero.

For example, G(p) = 3 + 2g^1 , and m = 2, then S(g) = 4g^2 + 12g + 9, so the coefficients of S(g) are {4, 12, 9}; G(p) = 3 + 2g^1 , and m = 3, then S(g) = 8g^3 + 36g^2 + 54g + 27, so the coefficients of S(g) are { 8, 36, 54, 27 }.

The coefficients may be so large, so hwh wants to know the coefficients (mod 211812353).

Input

In the first line one integer T indicates the number of test cases. (T <= 1000)

For every case, two integers n and m in a single line, indicate the number of element of the G(p) and the value of m. (2 <= n <= 10^5, 1 <= m <= 50000, n * m <= 10^5)

Then one line has n integers Ki, indicates the i-th coefficient of G(p). (0 <= Ki <= 10^9)

Output

For each test case, output (n – 1)*m + 1 lines, the i-th (i >= 0) line output “[i] = ci”, where ci is the coefficient of g^i in S(g)

Output one blank line after each test case.

Sample Input

2 2 2 3 2 2 3 3 2

Sample Output

[0] = 9 [1] = 12 [2] = 4 [0] = 27 [1] = 54 [2] = 36 [3] = 8

Source

FOJ有奖月赛-2011年03月

Submit  Back  Status  Discuss