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

见题面

见题面