Add

I: Add

Problem Statement

Mr. T has had an integer sequence of N elements a_1, a_2, ... , a_N and an integer K. Mr. T has created N integer sequences B_1, B_2, ... , B_N such that B_i has i elements.

• B_{N,j} = a_j (1 \leq j \leq N)
• B_{i,j} = K \times B_{i+1,j} + B_{i+1,j+1} (1\leq i \leq N-1, 1 \leq j \leq i)

Mr. T was so careless that he lost almost all elements of these sequences a and B_i. Fortunately, B_{1,1}, B_{2,1}, ... , B_{N,1} and K are not lost. Your task is to write a program that restores the elements of the initial sequence a for him. Output the modulo 65537 of each element instead because the absolute value of these elements can be extremely large. More specifically, for all integers i (1 \leq i \leq N), output r_i that satisfies r_i $\equiv$ a_i $\bmod \;$ 65537, 0 \leq r_i < 65537. Here, we can prove that the original sequence Mr. T had can be uniquely determined under the given constraints.

Input

T N_1 K_1 C_{1,1} C_{1,2} ... C_{1,N} N_2 K_2 C_{2,1} C_{2,2} ... C_{2,N} : N_T K_T C_{T,1} C_{T,2} ... C_{T,N}

The first line contains a single integer T that denotes the number of test cases. Each test case consists of 2 lines. The first line of the i-th test case contains two integers N_i and K_i. The second line of the i-th test case contains N_i integers C_{i,j} (1 \leq j \leq N_i). These values denote that N = N_i , K = K_i , B_{j,1} = C_{i,j} (1 \leq j \leq N_i) in the i-th test case.

Constraints

• 1 \leq T \leq 10
• 1 \leq N \leq 50000
• |K| \leq 10^9
• |B_{i,1}| \leq 10^9
• All input values are integers.

Output

Output T lines. For the i-th line, output the answer for the i-th test case a_1, a_2, ..., a_N in this order. Each number must be separated by a single space.

Sample Input 1

2 3 0 1 2 3 3 1 1 2 3

Output for Sample Input 1

3 2 1 3 65536 0

Example

Input

2 3 0 1 2 3 3 1 1 2 3

Output

3 2 1 3 65536 0

inputFormat

outputFormat

Output the modulo 65537 of each element instead because the absolute value of these elements can be extremely large. More specifically, for all integers i (1 \leq i \leq N), output r_i that satisfies r_i $\equiv$ a_i $\bmod \;$ 65537, 0 \leq r_i < 65537. Here, we can prove that the original sequence Mr. T had can be uniquely determined under the given constraints.

Input

T N_1 K_1 C_{1,1} C_{1,2} ... C_{1,N} N_2 K_2 C_{2,1} C_{2,2} ... C_{2,N} : N_T K_T C_{T,1} C_{T,2} ... C_{T,N}

The first line contains a single integer T that denotes the number of test cases. Each test case consists of 2 lines. The first line of the i-th test case contains two integers N_i and K_i. The second line of the i-th test case contains N_i integers C_{i,j} (1 \leq j \leq N_i). These values denote that N = N_i , K = K_i , B_{j,1} = C_{i,j} (1 \leq j \leq N_i) in the i-th test case.

Constraints

• 1 \leq T \leq 10
• 1 \leq N \leq 50000
• |K| \leq 10^9
• |B_{i,1}| \leq 10^9
• All input values are integers.

Output

Output T lines. For the i-th line, output the answer for the i-th test case a_1, a_2, ..., a_N in this order. Each number must be separated by a single space.

Sample Input 1

2 3 0 1 2 3 3 1 1 2 3

Output for Sample Input 1

3 2 1 3 65536 0

Example

Input

2 3 0 1 2 3 3 1 1 2 3

Output

3 2 1 3 65536 0

样例

2
3 0
1 2 3
3 1
1 2 3

3 2 1
3 65536 0

</p>