Problem: 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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

struct node{
	ld x,y;
	node(ld x=0,ld y=0):x(x),y(y){}
	node operator+(const node c)const{return node(x+c.x,y+c.y);}
	node operator-(const node c)const{return node(x-c.x,y-c.y);}
	node operator*(const node c)const{return node(x*c.x-y*c.y,x*c.y+y*c.x);}
}A[150000],B[150000];

const int cys=65537;
const ld pi=acos(-1);
int n,k,N,l;
int r[150000],a[150000];
ll fac[150000],inv[150000];

ll qpow(ll x,ll p){
	ll ret=1;
	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
	return ret;
}

void fft(node *A,int N,int f){
	for(int i=0;i<N;i++) if(i<r[i]) swap(A[i],A[r[i]]);
	for(int i=1;i<N;i<<=1){
		node wn(cos(pi/i),f*sin(pi/i));
		for(int j=0;j<N;j+=(i<<1)){
			node w(1,0);
			for(int k=j;k<j+i;k++,w=w*wn){
				node x=A[k],y=w*A[k+i];
				A[k]=x+y; A[k+i]=x-y;
			}
		}
	}
	if(f<0){
		for(int i=0;i<N;i++) A[i].x/=N;
	}
}

int main(){
	int T=readint();
	while(T--){
		n=readint(); k=(readint()%cys+cys)%cys;
		fac[0]=inv[0]=1;
		for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%cys;
		inv[n]=qpow(fac[n],cys-2);
		for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
		for(int i=0;i<n;i++) a[i]=(readint()%cys+cys)%cys;
		l=0;
		for(N=1;N<n+n;N<<=1) l++;
		for(int i=0;i<N;i++) A[i]=B[i]=node(0,0);
		for(int i=0;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
		ll now=1;
		for(int i=0;i<n;i++){
			A[i].x=inv[i]*a[n-i-1]%cys;
			B[i].x=inv[i]*now%cys;
			if(i&1) B[i].x=(cys-(ll)B[i].x)%cys;
			now=now*k%cys;
		}
		fft(A,N,1); fft(B,N,1);
		for(int i=0;i<N;i++) A[i]=A[i]*B[i];
		fft(A,N,-1);
		for(int i=0;i<n;i++){
			printf("%lld",fac[i]*((ll)(A[i].x+0.5)%cys)%cys);
			if(i!=n-1) printf(" ");
		}
		printf("\n");
	}
	return 0;
}